fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define pb push_back
  4. #define F first
  5. #define S second
  6. #define yes cout << "YES" << "\n"
  7. #define no cout << "NO" << "\n"
  8. #define answer cout << ans1 << "\n"
  9. #define db long double
  10. using namespace std;
  11.  
  12.  
  13. ll n,m,a,b,c,d,k,w,x,y,z,ans1,q,T;
  14. bool f=0;
  15. char cc;
  16. const int N=1e6 + 10 , LOG = 20;
  17. const int mod = 998244353;
  18. vector<int> g[N];
  19. int in[N],out[N];
  20.  
  21. struct segtree
  22. {
  23.   int sz;
  24.   vector<ll> sums;
  25.   void init(int n){sz=1;while(sz<n)sz*=2;sums.assign(2*sz,0);}
  26.  
  27.   void put(int lx,int rx,ll x,int v,int l,int r)
  28.   {
  29.     if(l>=lx && r<=rx){sums[v]+=x; return;}
  30.     if(l>=rx || r<=lx){return;}
  31.     int m=(l+r)/2;
  32.     put(lx,rx,x,2*v+1,l,m);
  33.     put(lx,rx,x,2*v+2,m,r);
  34.   }
  35.  
  36.   void put(int lx,int rx,ll x)
  37.   {
  38.     put(lx,rx,x,0,0,sz);
  39.   }
  40.  
  41.   ll get_Sum(int i,int v,int l,int r)
  42.   {
  43.     if(r-l==1){return sums[v];}
  44.     int m = (l+r)/2;
  45.     ll ret = sums[v];
  46.     if(i<m)ret += get_Sum(i,2*v+1,l,m);
  47.     else ret += get_Sum(i,2*v+2,m,r);
  48.     return ret;
  49.   }
  50.  
  51.   ll get_Sum(int i)
  52.   {
  53.     return get_Sum(i,0,0,sz);
  54.   }
  55. } sg;
  56.  
  57. void dfs(int v,int p=0)
  58. {
  59.   in[v] = ++T;
  60.   for(auto x : g[v])
  61.   {
  62.     if(x==p){continue;}
  63.     dfs(x,v);
  64.   }
  65.   out[v] = T;
  66. }
  67.  
  68. void solve()
  69. {
  70.   cin >> n >> q;
  71.   for(int i=0;i<n-1;++i)
  72.   {
  73.     cin >> a >> b;
  74.     g[a].push_back(b);
  75.     g[b].push_back(a);
  76.   }
  77.   dfs(1);
  78.   sg.init(n+2);
  79.   while(q--)
  80.   {
  81.     cin >> a;
  82.     if(a==1)
  83.     {
  84.       int v,x;
  85.       cin >> v >> x;
  86.       sg.put(in[v],out[v]+1,x);
  87.     }
  88.     else
  89.     {
  90.       int v;
  91.       cin >> v;
  92.       cout << sg.get_Sum(in[v]) << "\n";
  93.     }
  94.   }
  95. }
  96.  
  97. int main(){
  98.   ios_base::sync_with_stdio(NULL);cin.tie(0);cout.tie(0);
  99.   int tt=1,var=0;
  100. //  cin >> tt;
  101.   while(tt--)
  102.   {
  103.     solve();
  104.   }
  105.   return 0;
  106. }
  107.  
Success #stdin #stdout 0.01s 29828KB
comments (?)
stdin
copy 
7 7
1 7
7 2
7 5
3 4
3 6
1 3
1 1 2
1 2 11
2 7
1 3 9
2 5
2 6
2 4
stdout
copy 
2
2
11
11
https://ideone.com/i0ONH3
language:
C++14 (gcc 8.3)
created:
327 days ago
visibility:
secret

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!