fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int lli;
  4. typedef long double ld;
  5. /*
  6. #include <chrono> 
  7. using namespace std::chrono;
  8. #include <boost/multiprecision/cpp_int.hpp> 
  9. using namespace boost::multiprecision;
  10. #include <ext/pb_ds/assoc_container.hpp> 
  11. #include <ext/pb_ds/tree_policy.hpp> 
  12. using namespace __gnu_pbds; 
  13. #define ordered_set tree<lli, null_type,less_equal<lli>, rb_tree_tag,tree_order_statistics_node_update> 
  14. //remove _equal from less_equal to make it ordered set , currently it is ordered_multiset
  15. */
  16. #define pb push_back
  17. const lli mod=1e9+7;
  18. const lli mod1=998244353;
  19. #define fir first
  20. #define sec second
  21. #define plli pair<lli,lli>
  22. #define pplli pair<lli,plli>
  23. /*
  24. lli power(lli a, lli b) {
  25.     lli res = 1;
  26.     while (b > 0) {
  27.         if (b & 1)
  28.             res = res * a;
  29.         a = a * a;
  30.         b >>= 1;
  31.     }
  32.     return res;
  33. }
  34. lli powermod(lli a, lli b) 
  35. {
  36.     lli res = 1;
  37.     while (b > 0) {
  38.         if (b & 1)
  39.             res = ((res%mod)*(a%mod))%mod;
  40.         a = (a * a)%mod;
  41.         b >>= 1;
  42.     }
  43.     return res%mod;
  44. }
  45. */
  46. const lli N=200001;
  47. vector<lli> v[N];
  48. lli timer=1;
  49. lli sub[N],a[N],in[N],val[N];
  50. vector<lli> flat;
  51. lli st[4*N],lazy[4*N];
  52.  
  53. lli dfs(lli node,lli par,lli x=0)
  54. {
  55.     in[node]=timer;
  56.     timer++;
  57.     flat.pb(node);
  58.     sub[node]=1;
  59.     val[node]=x+a[node];
  60.     for(lli child:v[node])
  61.     {
  62.         if(child!=par)
  63.         {
  64.             dfs(child,node,x+a[node]);
  65.             sub[node]+=sub[child];
  66.         }
  67.     }
  68.     return 0;
  69. }
  70.  
  71. lli build(lli ss,lli se,lli z)
  72. {
  73.     if(ss==se)
  74.     {
  75.         st[z]=val[flat[ss]];
  76.         return 0;
  77.     }
  78.     lli mid=(ss+se)/2;
  79.     build(ss,mid,z*2);
  80.     build(mid+1,se,(z*2)+1);
  81.     st[z]=st[z*2]+st[z*2+1];
  82.     return 0;
  83. }
  84.  
  85. void push(lli z)
  86. {
  87.     st[z*2]+=lazy[z];
  88.     lazy[z*2]+=lazy[z];
  89.     st[z*2+1]+=lazy[z];
  90.     lazy[z*2+1]+=lazy[z];
  91.     lazy[z]=0;
  92. }
  93.  
  94. lli update(lli ss,lli se,lli z,lli qs,lli qe,lli add)
  95. {
  96.     if((ss>qe)||(se<qs))
  97.         return 0;
  98.     if((ss>=qs)and(se<=qe))
  99.     {
  100.         st[z]+=add;
  101.         lazy[z]+=add;
  102.         return 0;
  103.     }
  104.     push(z);
  105.     lli mid=(ss+se)/2;
  106.     update(ss,mid,z*2,qs,qe,add);
  107.     update(mid+1,se,z*2+1,qs,qe,add);
  108.     st[z]=st[z*2]+st[z*2+1];
  109.     return 0;
  110. }
  111.  
  112. lli query(lli ss,lli se,lli z,lli qs)
  113. {
  114.     if(ss==se)
  115.         return st[z];
  116.     lli mid=(ss+se)/2;
  117.     push(z);
  118.     if(qs<=mid)
  119.         return query(ss,mid,z*2,qs);
  120.     else
  121.         return query(mid+1,se,z*2+1,qs);
  122. }
  123.  
  124. int main()
  125. {
  126.     ios_base::sync_with_stdio(false);
  127.     cin.tie(NULL);
  128.     lli T,i,j;
  129.     T=1;
  130.     while(T--)
  131.     {
  132.         flat.pb(0);
  133.         lli n,q,x,y;
  134.         cin>>n>>q;
  135.         for(i=1;i<=n;i++)
  136.             cin>>a[i];
  137.         for(i=0;i<n-1;i++)
  138.         {
  139.             cin>>x>>y;
  140.             v[x].pb(y);
  141.             v[y].pb(x);
  142.         }
  143.         dfs(1,0);
  144.         build(1,n,1);
  145.         while(q--)
  146.         {
  147.             lli r,s;
  148.             cin>>r;
  149.             if(r==1)
  150.             {
  151.                 cin>>s>>x;
  152.                 update(1,n,1,in[s],in[s]+sub[s]-1,x-a[s]);
  153.                 a[s]=x;
  154.             }
  155.             else if(r==2)
  156.             {
  157.                 cin>>s;
  158.                 cout<<query(1,n,1,in[s])<<"\n";
  159.             }
  160.         }
  161.     }
  162.     return 0;
  163. }
  164.  
  165.  
  166.  
Success #stdin #stdout 0.01s 17184KB
comments (?)
stdin
copy 
5 3
4 2 5 2 1
1 2
1 3
3 4
3 5
2 4
1 3 2
2 4
stdout
copy 
11
8
https://ideone.com/2Oxgwm
language:
C++14 (gcc 8.3)
created:
3 years 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!