fork download
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define mod 1000000007
  4. #define pb push_back
  5. #define fi first
  6. #define se second
  7. #define fr(i,s,e) for(i=s;i<e;i++)
  8. #define ms(arr,val) memset(arr,val,sizeof(arr))
  9. using namespace std;
  10. const ll range=100005;
  11. vector<ll> tree[range];
  12. ll par[range],st[4*range],tin[range],depth[range],child[range],chain[range],head[range];
  13. ll timer=0,c=0,n;
  14. void dfs(ll u,ll p,ll d)
  15. {
  16. depth[u]=d;
  17. child[u]=1;
  18. par[u]=p;
  19. for(ll v:tree[u])
  20. {
  21. if(v==p)
  22. continue;
  23. dfs(v,u,d+1);
  24. //par[v]=u;
  25. child[u]+=child[v];
  26. }
  27. }
  28. void hld(ll u,ll p)
  29. {
  30. if(head[c]==-1)
  31. head[c]=u;
  32. chain[u]=c;
  33. tin[u]=++timer;
  34. ll special=-1;
  35. for(ll v:tree[u])
  36. {
  37. if(v==p)
  38. continue;
  39. if(special==-1||child[special]<child[v])
  40. special=v;
  41. }
  42. if(special!=-1)
  43. hld(special,u);
  44. for(ll v:tree[u])
  45. {
  46. if(v==p||v==special)
  47. continue;
  48. c++;
  49. hld(v,u);
  50. }
  51. }
  52. ll lca(ll u,ll v)
  53. {
  54. while(head[chain[u]]!=head[chain[v]]){
  55. if(depth[head[chain[u]]]<depth[head[chain[v]]]) v=par[head[chain[v]]];
  56. else u=par[head[chain[u]]];
  57. }
  58. return depth[u]>depth[v]? v:u;
  59. }
  60. /*
  61. ll lca(ll u,ll v,vector<bool> vis)
  62. {
  63.   if(depth[u]<depth[v])
  64.   swap(u,v);
  65.   while(u!=-1)
  66.   {
  67.   vis[u]=1;
  68.   u=par[u];
  69.   }
  70.   while(1)
  71.   {
  72.   if(vis[v])
  73.   return v;
  74.   v=par[v];
  75.   }
  76.   return 1;
  77. }
  78. */
  79. ll query(ll ss,ll se,ll si,ll l,ll r)
  80. {
  81. if(l<=ss&&r>=se)
  82. return st[si];
  83. if(l>se||r<ss)
  84. return 0;
  85. ll mid=(ss+se)>>1;
  86. return max(query(ss,mid,si+si,l,r),query(mid+1,se,si+si+1,l,r));
  87. }
  88. ll crawl(ll u,ll v)
  89. {
  90. ll ans=0;
  91. while(1)
  92. {
  93. if(chain[u]==chain[v])
  94. {
  95. return max(ans,query(1,n,1,tin[v],tin[u]));
  96. }
  97. ans=max(ans,query(1,n,1,tin[head[chain[u]]],tin[u]));
  98. u=par[head[chain[u]]];
  99. }
  100. return ans;
  101. }
  102. ll ans(ll u,ll v)
  103. {
  104. ll ans=lca(u,v);
  105. return max(crawl(u,ans),crawl(v,ans));
  106. }
  107. void update(ll ss,ll se,ll si,ll i,ll val)
  108. {
  109. if(i>se||i<ss)
  110. return ;
  111. if(se==ss && ss==i) {st[si]+=val;return;}
  112. ll mid=(ss+se)>>1;
  113. update(ss,mid,2*si,i,val);
  114. update(mid+1,se,2*si+1,i,val);
  115. st[si]=max(st[2*si],st[2*si+1]);
  116. //st[si]=max(update(ss,mid,si+si,i,val),update(mid+1,se,si+si+1,i,val));
  117. }
  118. int main(){
  119. ios_base::sync_with_stdio(false);
  120. cin.tie(0);
  121. cout.tie(0);
  122. ll t=1;
  123. //cin>>t;
  124. while(t--){
  125. ll i,u,v,q;
  126. cin>>n;
  127. fr(i,0,n-1)
  128. {
  129. cin>>u>>v;
  130. tree[u].pb(v);
  131. tree[v].pb(u);
  132. //par[i+1]=head[i+1]=-1;
  133. }
  134. //head[1]=-1;
  135. ms(head,-1);
  136. ms(st,0);
  137. dfs(1,-1,0);
  138. //par[1]=-1;
  139. hld(1,1);
  140. cin>>q;
  141. vector<bool> vis(range,0);
  142. while(q--)
  143. {
  144. char g;
  145. cin>>g>>u>>v;
  146. if(g=='I')
  147. update(1,n,1,tin[u],v);
  148. else
  149. cout<<ans(u,v)<<"\n";
  150. // fr(i,0,2*timer)
  151. // cout<<st[i]<<" ";
  152. // cout<<"\n";
  153. }
  154. }
  155. return 0;
  156. }
Success #stdin #stdout 0.01s 9432KB
stdin
4
1 2
2 3
2 4
6
I 1 1
G 1 1
G 3 4
I 2 3
G 1 1
G 3 4
stdout
1
0
1
3