fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define task "main"
  3. #define multi 0
  4. using namespace std;
  5. using ll = long long int;
  6. using ld = long double;
  7. using pll = pair<ll,ll>;
  8. using pld = pair<ld,ld>;
  9. const ll maxn = 2e5 + 5;
  10. const ll mod  = 1e9 + 7;
  11. const ll INF = 1e18;
  12. const ll maxlog = 21;
  13.  
  14. ll n, q;
  15. ll a[maxn] , tin[maxn] , tout[maxn];
  16. vector<ll> adj[maxn];
  17. ll ti = 0;
  18. void dfs(ll u , ll p)
  19. {
  20.     tin[u] = ti;
  21.     ti++;
  22.     for(ll v: adj[u])
  23.     {
  24.         if(v!= p)
  25.         {
  26.             dfs(v,u);
  27.         }
  28.     }
  29.     tout[u] = ti;
  30. }
  31.  
  32. struct segment
  33. {
  34.     vector<ll>t;
  35.     void tao(ll n)
  36.     {
  37.         t.resize(4*n);
  38.     }
  39.     void update(ll id , ll l , ll r , ll pos , ll val)
  40.     {
  41.         if(l == r) t[id] = val;
  42.         else
  43.         {
  44.             ll mid = (l+r) >> 1;
  45.             if(pos <= mid) update(2*id,l,mid,pos,val);
  46.             else update(2*id+1,mid+1,r,pos,val);
  47.             t[id] = t[2*id+1] + t[2*id];
  48.         }
  49.     }
  50.     ll query(ll id , ll l , ll r , ll u , ll v)
  51.     {
  52.         if(u<=l && r <=v) return t[id];
  53.         if(r<u || v<l) return 0;
  54.         ll mid = (l+r) >> 1;
  55.         ll t1 = query(2*id,l,mid,u,v);
  56.         ll t2 = query(2*id+1,mid+1,r,u,v);
  57.         return t1 + t2;
  58.     }
  59. };
  60.  
  61. void solve()
  62. {
  63.     cin>>n>>q;
  64.     for(ll i = 1 ; i<=n ; i++) cin>>a[i];
  65.     for(ll i = 1; i<n ; i++)
  66.     {
  67.         ll u , v;
  68.         cin>>u>>v;
  69.         adj[u].push_back(v);
  70.         adj[v].push_back(u);
  71.     }
  72.     dfs(1,-1);
  73.     segment seg;
  74.     seg.tao(n);
  75.     for(ll i = 1; i<=n ; i++)
  76.     {
  77.         seg.update(1,0,n-1,tin[i] , a[i]);
  78.     }
  79.     while(q--)
  80.     {
  81.         ll type; cin>>type;
  82.         if(type == 1)
  83.         {
  84.             ll s , x;
  85.             cin>>s>>x;
  86.             seg.update(1,0,n-1,tin[s] , x);
  87.         }
  88.         else
  89.         {
  90.             ll u; cin>>u;
  91.             cout<<seg.query(1,0,n-1,tin[u] , tout[u] - 1) << '\n';
  92.         }
  93.     }
  94.  
  95.  
  96.  
  97.  
  98.  
  99. }
  100.  
  101. int main()
  102. {
  103.     if(fopen(task".inp" , "r"))
  104.     {
  105.         freopen(task".inp" , "r" , stdin);
  106.         freopen(task".out" , "w" , stdout);
  107.         freopen(task".err" , "w" , stderr);
  108.     }
  109.     int tt = 1;
  110.     if(multi)cin>>tt;
  111.     while(tt--)
  112.     {
  113.         solve();
  114.     }
  115. }
  116.  
Success #stdin #stdout 0.01s 10788KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ZRyGqk
language:
C++14 (clang 8.0)
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!