fork download
copy 
  1. //submitted by HimJ
  2. #include<bits/stdc++.h>
  3. #define ll long long
  4. #define mod 1000000007
  5. #define pb push_back
  6. #define fi first
  7. #define se second
  8. #define fr(i,s,e) for(i=s;i<e;i++)
  9. #define ms(arr,val) memset(arr,val,sizeof(arr))
  10. using namespace std;
  11. const ll range=100005;
  12. vector<ll> tree[range];
  13. ll par[range],st[4*range],tin[range],depth[range],child[range],chain[range],head[range];
  14. ll timer=0,c=0,n;
  15. void dfs(ll u,ll p,ll d)
  16. {
  17.     depth[u]=d;
  18.     child[u]=1;
  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,vector<bool> vis)
  53. {
  54.     if(depth[u]<depth[v])
  55.         swap(u,v);
  56.     while(u!=-1)
  57.     {
  58.         vis[u]=1;
  59.         u=par[u];
  60.     }
  61.     while(1)
  62.     {
  63.         if(vis[v])
  64.             return v;
  65.         v=par[v];
  66.     }
  67.     return 1;
  68. }
  69. ll query(ll ss,ll se,ll si,ll l,ll r)
  70. {
  71.     if(l<=ss&&r>=se)
  72.         return st[si];
  73.     if(l>se||r<ss)
  74.         return 0;
  75.     ll mid=(ss+se)>>1;
  76.     return max(query(ss,mid,si+si,l,r),query(mid+1,se,si+si+1,l,r));
  77. }
  78. ll crawl(ll u,ll v)
  79. {
  80.     ll ans=0;
  81.     while(1)
  82.     {
  83.         if(chain[u]==chain[v])
  84.         {
  85.             return max(ans,query(1,n,1,tin[v],tin[u]));
  86.         }
  87.         ans=max(ans,query(1,n,1,tin[head[chain[u]]],tin[u]));
  88.         u=par[head[chain[u]]];
  89.     }
  90.     return ans;
  91. }
  92. ll ans(ll u,ll v,vector<bool> vis)
  93. {
  94.     ll ans=lca(u,v,vis);
  95.     return max(crawl(u,ans),crawl(v,ans));
  96. }
  97. ll update(ll ss,ll se,ll si,ll i,ll val)
  98. {
  99.     if(i>se||i<ss)
  100.         return 0;
  101.     if(se==ss)
  102.         return st[si]+=val;
  103.     ll mid=(ss+se)>>1;
  104.     return st[si]=max(update(ss,mid,si+si,i,val),update(mid+1,se,si+si+1,i,val));
  105. }
  106. int main(){
  107.     ios_base::sync_with_stdio(false);
  108.     cin.tie(0);
  109.     cout.tie(0);
  110.   ll t=1;
  111.   //cin>>t;
  112.     while(t--){
  113.             ll i,u,v,q;
  114.             cin>>n;
  115.             fr(i,0,n-1)
  116.             {
  117.                 cin>>u>>v;
  118.                 tree[u].pb(v);
  119.                 tree[v].pb(u);
  120.                 par[i+1]=head[i+1]=-1;
  121.             }
  122.             ms(st,0);
  123.             dfs(1,1,0);
  124.             par[1]=-1;
  125.             hld(1,1);
  126.             cin>>q;
  127.             vector<bool> vis(range,0);
  128.             while(q--)
  129.             {
  130.                 char g;
  131.                 cin>>g>>u>>v;
  132.                 if(g=='I')
  133.                     update(1,n,1,tin[u],v);
  134.                 else
  135.                     cout<<ans(u,v,vis)<<"\n";
  136. //	fr(i,0,2*timer)
  137. //	cout<<st[i]<<" ";
  138. //	cout<<"\n";
  139.             }
  140.   }
  141.   return 0;
  142.   }
  143.  
  144.  
Runtime error #stdin #stdout 0s 26224KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/1mZoQh
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!