PROBLEM LINK:
Practice Link
Vidit and Einstein
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
DIFFICULTY:
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[0]=U, max[1]= 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[3]=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[2][2], ll M[2][2])
{
ll x = (((F[0][0]+mod)%mod * (M[0][0]+mod)%mod)%mod + ((F[0][1]+mod)%mod * (M[1][0]+mod)%mod)%mod)%mod;
ll y = (((F[0][0]+mod)%mod * (M[0][1]+mod)%mod)%mod + ((F[0][1]+mod)%mod * (M[1][1]+mod)%mod)%mod)%mod;
ll z = (((F[1][0]+mod)%mod * (M[0][0]+mod)%mod)%mod + ((F[1][1]+mod)%mod * (M[1][0]+mod)%mod)%mod)%mod;
ll w = (((F[1][0]+mod)%mod * (M[0][1]+mod)%mod)%mod + ((F[1][1]+mod)%mod * (M[1][1]+mod)%mod)%mod)%mod;
F[0][0] = x%mod;
F[0][1] = y%mod;
F[1][0] = z%mod;
F[1][1] = w%mod;
}
void powerm(ll F[2][2], ll n,ll gg)
{
if(n == 0 || n == 1)
return;
ll M[2][2] = {{1, 1}, {1, 0}};
ll pk[2][2]={{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[2][2] = {{1, 1}, {1, 0}};
if (n == 0)
return 0;
powerm(F, n - 1,gg);
return F[0][0];
}
static vector<ll>g1[200003];
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[2][2]={{3,1},{0,1}};
powerm(dp,t,0);
ll a2=(((dp[0][0]+mod)%mod*sm0%mod)%mod+((dp[0][1]+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
// your code goes here
return 0;
}
.