fork download
copy 
  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
comments (?)
stdin
copy 
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
copy 
1
0
1
3
https://ideone.com/eIEV8s
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!