We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
#include<bits/stdc++.h>usingnamespacestd;#define rep(i, a, b) for(int i = a; i < b; i++)#define S(x) scanf("%d",&x)#define P(x) printf("%d\n",x)typedeflonglongintLL;constintmod=1000000007;constintMAXN=100005;vector<int>g[MAXN];intdep[MAXN];intP[MAXN];int_tm;inttin[2*MAXN];inttout[2*MAXN];intn;intL[MAXN][25];LLbit1[2*MAXN],bit2[2*MAXN],bit3[2*MAXN];LL_pow(LLa,LLb){if(!b)return1;if(b==1)returna;if(b==2)return(a*a)%mod;if(b&1)return(a*_pow(a,b-1))%mod;return_pow(_pow(a,b/2),2);}voiddfs(intc,intp,intd){P[c]=p;dep[c]=d;_tm++;tin[c]=_tm;rep(i,0,g[c].size()){intu=g[c][i];if(u!=p)dfs(u,c,d+1);}_tm++;tout[c]=_tm;}voidprocessLca(){inti,j;//we initialize every element in P with -1intN=n;for(i=0;i<n;i++)for(j=0;1<<j<N;j++)L[i][j]=-1;//the first ancestor of every node i is T[i]for(i=0;i<N;i++)L[i][0]=P[i];//bottom up dynamic programingfor(j=1;1<<j<N;j++)for(i=0;i<N;i++)if(L[i][j-1]!=-1)L[i][j]=L[L[i][j-1]][j-1];}intlca(intp,intq){inttmp,log,i;//if p is situated on a higher level than q then we swap themif(dep[p]<dep[q])tmp=p,p=q,q=tmp;//we compute the value of [log(L[p)]for(log=1;1<<log<=dep[p];log++);log--;//we find the ancestor of node p situated on the same level//with q using the values in Pfor(i=log;i>=0;i--)if(dep[p]-(1<<i)>=dep[q])p=L[p][i];if(p==q)returnp;//we compute LCA(p, q) using the values in Pfor(i=log;i>=0;i--)if(L[p][i]!=-1&&L[p][i]!=L[q][i])p=L[p][i],q=L[q][i];returnP[p];}voidupdate(LL*bit,intidx,LLval){for(inti=idx;i<=_tm;i+=i&-i)bit[i]+=val;}LLquery(LL*bit,intidx){LLres=0;for(inti=idx;i;i-=i&-i){res+=bit[i];}returnres%mod;}LLQQQ(intx){LLres;LLc=dep[x];res=(query(bit1,tin[x])*c)%mod;res+=(query(bit2,tin[x])*(((LL)c*c)%mod));res%=mod;res+=query(bit3,tin[x]);returnres%mod;}intmain(){inte,r;scanf("%d%d%d",&n,&e,&r);r--;rep(i,0,n-1){intx,y;scanf("%d%d",&x,&y);x--;y--;g[x].push_back(y);g[y].push_back(x);}dfs(r,-1,0);processLca();while(e--){chars[5];scanf("%s",s);if(s[0]=='U'){intT,V,K;scanf("%d%d%d",&T,&V,&K);T--;LLk=((LL)K*_pow(2,mod-2))%mod;LLp=dep[T];LLval;val=(V-2*p*k+k)%mod;val=(val+mod)%mod;update(bit1,tin[T],val);update(bit1,tout[T]+1,-val);val=k;update(bit2,tin[T],val);update(bit2,tout[T]+1,-val);val=(p*p)%mod;val=(val*k)%mod;val-=p*(V+k);val%=mod;val+=mod+V;val%=mod;update(bit3,tin[T],val);update(bit3,tout[T]+1,-val);}else{intA,B;scanf("%d%d",&A,&B);A--;B--;LLans=0;intl=lca(A,B);ans=QQQ(A)+QQQ(B)-QQQ(l);if(P[l]!=-1)ans-=QQQ(P[l]);ans%=mod;ans+=mod;ans%=mod;printf("%lld\n",ans);}}return0;}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Rooted Tree
You are viewing a single comment's thread. Return to all comments →
Solution in C++