 # VIQUE - Editorial

Author: valiant_vidit
Editorialist: valiant_vidit
Tester: valiant_vidit

# PROBLEM:

Given a tree with N nodes which are numbered as 1 to N . The beauty of the tree is defined as sum of all the values of the nodes of tree.

An operation defined on the tree :

Lets consider an edge E joining 2 nodes with value U and V, then a new node is inserted between the edge whose value is equal to U+V.
In others words, a new node with value U+V appears such that there is an edge between U and U+V , and between V and U+V.

This operation is to be performed till S second simultaneously on each edge.

After S second, To find the summation of beauty and max value of node of the tree.

# PREREQUISITES:

• Matrix Exponentiation
• Number Theory

EASY-MEDIUM

# EXPLANATION:

First let the beauty of the tree at ith second be dp_{i}.
We can observe that the new nodes which will form after 0 second will have degree of only 2 , so the contribution of any node U (except the nodes at S=0)
will be exactly 3 times their value in dp_{i+1}. Now lets calculate the contribution of those nodes which have degree not equal to 2.
So for them we can let that their contribution is 3 times their value (by assuming their degree = 2 and one itself), and then we can iterate over all initial edges to find
out their extra contribution in next state ( that may be positive or negative depending on their magnitude and degree), which we will compute initially and treat it as constant value (k) for the recurrence relation:
dp[i+1]=3*dp[i] + k;
as the value of i is very high we will compute dp[i] through matrix exponentiation.

Now, we have to compute maximum value of node at current time, will be the summation of last 2 consecutive max values multiplied by the fibonacci coefficients.

Let us consider for any edge E have nodes U and V (U>V), the max=U, max= U+V,
We can say that operations performed on an edge are independent to any other edge, as values will grow within the edge , we will see that
max=2*U+V i.e.( sum of U and U+V), thereby the max value within any edge will be summation of the previous 2 max values within that edge as the last 2 max values
will be adjacent to each other, like this for any edge E max value at any second S, = f(s)*V+f(s+1)*U, so the max value among all node at S will be
computed by iterating over all edge, thereby find the max among them on S second.But due as the value of S is large so max can not be calculated directly comparing them, so here we have use some basic mathematics, we can easily compute fibonacci numbers till 40 (which are less than the order 10^{9}) so till S=39 the answer can be computed directly,
Later we have to compare this value f(s)*V+f(s+1)*U,
=f(s)*((f(s)/f(s))*V+(f(s+1)/f(s))*U) = f(s)*(1*V+(phi)*U) ,
where phi will be approx 1.6180339887498948 i.e. golden ratio , for larger values of fibonacci numbers, by this keeping in mid we can compare the value and later find the max value of node of the tree.

# SOLUTION:

Setter's Solution in C++
``````/*author : vidit shukla

(valiant_vidit)*/

#pragma  GCC optimize("O3")

#include <bits/stdc++.h>

#define ll               long long int

#define ld               double

#define bhaago           ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

#define loop(a,b,i)      for(ll i=a;i<b;i++)

#define loop1(a,b,i)     for(ll i=a;i>b;i--)

#define printclock       cerr<<"Time : "<<1000*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";

#define endl              '\n'

#define Endl              '\n'

#define az(i)            for(auto it:i)cout<<it<<" ";cout<<Endl;

#define mpaz(i)          for(auto it:i)cout<<it.first<<"->"<<it.second<<endl;cout<<Endl;

#define araz(arr,i)      loop(0,i,j)cout<<arr[j]<<" ";cout<<Endl;

#define setin(s,i)       for(auto it:i)s.insert(it);

#define mpin(mp,i)       for(auto it:i)mp[it]++;

#define yy               cout<<"YES"<<endl

#define nn               cout<<"NO"<<endl

#define prn1(tk,ans)      cout<<"Case #"<<tk<<": "<<ans<<endl

#define prn(tk)          cout<<"Case #"<<tk<<": "

#define init(dp,i)       memset(dp,i,sizeof dp)

#define fix(f,n) std::fixed<<std::setprecision(n)<<f

const double pi = std::acos(-1);

using namespace std;

const ll mod = 1000000000+7;

//------------------------------------------------------

//------------------------------------------------------

//---------------------------------------------------

void multiply(ll F, ll M)

{

ll x = (((F+mod)%mod * (M+mod)%mod)%mod + ((F+mod)%mod * (M+mod)%mod)%mod)%mod;

ll y = (((F+mod)%mod * (M+mod)%mod)%mod + ((F+mod)%mod * (M+mod)%mod)%mod)%mod;

ll z =  (((F+mod)%mod * (M+mod)%mod)%mod + ((F+mod)%mod * (M+mod)%mod)%mod)%mod;

ll w =  (((F+mod)%mod * (M+mod)%mod)%mod + ((F+mod)%mod * (M+mod)%mod)%mod)%mod;

F = x%mod;

F = y%mod;

F = z%mod;

F = w%mod;

}

void powerm(ll F, ll n,ll gg)

{

if(n == 0 || n == 1)

return;

ll M = {{1, 1}, {1, 0}};

ll pk={{3,1},{0,1}};

powerm(F, n / 2,gg);

multiply(F, F);

if (n % 2 != 0)

{

if(gg&1)

multiply(F, M);//gg=1; for fibo

else    multiply(F, pk);//gg=0;

}

}

ll fb(ll n)

{

ll gg=1;//for fibo..1

ll F = {{1, 1}, {1, 0}};

if (n == 0)

return 0;

powerm(F, n - 1,gg);

return F;

}

static vector<ll>g1;

int main() {

//see if tcs are present or not.

bhaago;

// freopen("fftc4.txt","r",stdin);

// freopen("ffftgoldc4.out","w",stdout);

ll tc=1;

cin>>tc;

while(tc--)

{

ll n,t;

cin>>n>>t;

loop(0,n+1,i)g1[i].clear();

ll mx=0;

vector<pair<ll,ll>>vp;

loop(0,n-1,i){

ll aa,bb;cin>>aa>>bb;

vp.push_back({aa,bb});

ll a1=(fb(t)*min(aa,bb));

a1=(a1+(fb(t+1)*max(aa,bb)));

if(t<40)

{

if(fb(t)*min(aa,bb)+fb(t+1)*max(aa,bb)>fb(t)*min(vp[mx].first,vp[mx].second)+fb(t+1)*max(vp[mx].first,vp[mx].second))

{

mx=i;

}

}

else

{

double golden=1.6180339887498948;

if(min(aa,bb)+golden*max(aa,bb)>min(vp[mx].first,vp[mx].second)+golden*max(vp[mx].first,vp[mx].second))

{

mx=i;

}

}

g1[aa].push_back(bb);g1[bb].push_back(aa);

}

mx%=mod;

ll sm0=n*(n+1)/2;

sm0%=mod;

if(n==1)

{

cout<<1+1<<endl;continue;

}

else

{

if(t==0)

{

cout<<(sm0%mod+n)%mod<<endl;

}//t=0

else

{

ll k=0;

loop(1,n+1,it)

{

k=k+(it%mod*((ll)(g1[it].size())-2)%mod)%mod;

}

ll dp={{3,1},{0,1}};

powerm(dp,t,0);

ll a2=(((dp+mod)%mod*sm0%mod)%mod+((dp+mod)%mod*k%mod)%mod+mod)%mod;

ll amx=fb(t+1)*max(vp[mx].first,vp[mx].second)+fb(t)*min(vp[mx].first,vp[mx].second);

cout<<(a2%mod+amx%mod)%mod<<endl;

}

}

//cout<<fb(40)<<" //"<<endl;

}

printclock

return 0;

}
``````

So the max of weight is max of weight after module?
not before?

I don’t get how are you calculating the node with the maximum value after S seconds by just iterating it. The thing you are suggesting is that, we iterate over all edges given, multiply with the Fibonacci numbers and then find the max of them, but it is calculated under mod. So how again are we finding the node with the maximum value ?

Edit:

This simple example proves that your assumption to find the node with the maximum value is wrong.

``````1
8 2924
8 1
6 2
6 5
3 4
7 6
5 3
1 6
``````

Your code for the edge `7 6` gives the max value as `568534205`, whereas if you take `6 7` instead which should have yielded smaller result gives `964451189`.

Can anyone prove that it if is at all possible to find the node with the maximum value correctly after S seconds ?

1 Like

@heart_blue @ankurkayal
I apologize for the inconvenience caused due to that factor.I have made the corrections.
The solutions will be rejudged of this question.

@valiant_vidit The question to find the beauty of the tree was indeed great, I liked the problem very much except the second part bugged me out .

I guess now u have got the answer, I have updated the method to find the max value of node of the tree after S seconds.

Oh, our team passed in third submission after fixed

I hope you liked the problem. Why do we need to maximize the actual node sums using the golden ratio? We know that the max node will be in the format U * Fib(S + 1) + V * Fib(S). Because of this, the max node will always be made by edge U — V where the sum U + V is maximum and the individual values U and V are maximum. So, we can just find this edge and use the fibonacci coefficients to get the max node.

Sir, I am going off-topic but didn’t know what to do there is a ton of cheating going on in contests and every ques answer is made available on youtube during contests thus leading to sevese downfall in rating of those people who are attempting with honesty . Can you please do something about it .

No, this logic will not work.
Tc :

``````1
7 4
1 2
1 3
1 4
1 6
1 7
4 5

``````

In this case the desired output should be:

``````1506
``````

But according to your code, it is

``````1505
``````

Because you are considering the edge 4—5 whereas the optimal edge will be 1—7.

I have updated the TC’s now. It is just a coincidence that your incorrect logic has passed my randomly generated TCs.

Ah, thanks for double checking my code. I was really surprised when I got AC with my incorrect logic. Now it makes more sense.