fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4. int n,q,timer=0,tin[200005],tout[200005],arr[400005],st[2000006],lz[2000006];
  5. vector <int> ve[200005];
  6. void DFS(int u, int p)
  7. {
  8.     tin[u]=++timer,arr[tin[u]]=u;
  9.     for (int v : ve[u]) if (v!=p) DFS(v,u);
  10.     tout[u]=++timer,arr[tout[u]]=u;
  11. }
  12. void UPDATE(int id, int l, int r, int u, int v, int x)
  13. {
  14.     if (l>v || r<u) return;
  15.     else if (l>=u && r<=v)
  16.     {
  17.         st[id]+=x,lz[id]+=x;
  18.         return;
  19.     }
  20.     int mid=(l+r)/2;
  21.     st[id*2]+=lz[id],lz[id*2]+=lz[id],st[id*2+1]+=lz[id],lz[id*2+1]+=lz[id],lz[id]=0;
  22.     UPDATE(id*2,l,mid,u,v,x),UPDATE(id*2+1,mid+1,r,u,v,x);
  23.     st[id]=max(st[id*2],st[id*2+1]);
  24. }
  25. int GET(int id, int l, int r, int u, int v)
  26. {
  27.     if (l>v || r<u) return -1e18;
  28.     else if (l>=u && r<=v) return st[id];
  29.     int mid=(l+r)/2;
  30.     st[id*2]+=lz[id],lz[id*2]+=lz[id],st[id*2+1]+=lz[id],lz[id*2+1]+=lz[id],lz[id]=0;
  31.     return max(GET(id*2,l,mid,u,v),GET(id*2+1,mid+1,r,u,v));
  32. }
  33. signed main()
  34. {
  35.     ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
  36.     cin>>n;
  37.     for (int i=1;i<n;i++)
  38.     {
  39.         int u,v;
  40.         cin>>u>>v;
  41.         ve[u].push_back(v),ve[v].push_back(u);
  42.     }
  43.     DFS(1,0);
  44.     cin>>q;
  45.     for (int i=1;i<=q;i++)
  46.     {
  47.         int t;
  48.         cin>>t;
  49.         if (t==1)
  50.         {
  51.             int x,v;
  52.             cin>>x>>v;
  53.             UPDATE(1,1,2*n,tin[x],tout[x],v);
  54.         }
  55.         else
  56.         {
  57.             int x;
  58.             cin>>x;
  59.             cout<<GET(1,1,2*n,tin[x],tout[x])<<'\n';
  60.         }
  61.     }
  62.     return 0;
  63. }
Success #stdin #stdout 0.01s 13244KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/EALige
language:
C++14 (gcc 8.3)
created:
1 day 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!