fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define pb push_back
  5. #define el '\n'
  6. #define fast_io ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  7.  
  8. const int MAXN = 2e5 + 5;
  9.  
  10. int n,m;
  11. int a[MAXN];
  12. vector<int> ke[MAXN];
  13. int tin[MAXN],tout[MAXN];
  14. int timer;
  15. int st[MAXN];
  16.  
  17. void dfs(int u, int p){
  18.     tin[u] = tout[u] = ++timer;
  19.     for(int v : ke[u]){
  20.         if(v==p) continue;
  21.         dfs(v,u);
  22.         tout[u]=max(tout[u],tout[v]);
  23.     }
  24. }
  25.  
  26. void update(int id, int l, int r, int pos, int val){
  27.     if(pos>r||pos<r) return;
  28.     if(l<=pos&&pos<=r) {
  29.         st[pos] = val;
  30.         return;
  31.     }
  32.     int mid = (l+r)/2;
  33.     update(id*2,l,mid,pos,val);
  34.     update(id*2+1,mid+1,r,pos,val);
  35.     st[id]=st[id*2]+st[id*2+1];
  36. }
  37.  
  38. int get(int id, int l, int r, int u, int v){
  39.     if(l>v||r<u) return 0;
  40.     if(l<=u&&r<=v){
  41.         return st[id];
  42.     }
  43.     int mid = (l+r)/2;
  44.     return get(id*2,l,mid,u,v)+get(id*2+1,mid+1,r,u,v);
  45. }
  46.  
  47. main() {
  48.     fast_io;
  49.     cin >> n >> m;
  50.     for(int i=1;i<=n;i++){
  51.         cin >> a[i];
  52.     }
  53.     for(int i=1;i<n;i++){
  54.         int u,v;
  55.         cin >> u >> v;
  56.         ke[u].pb(v);
  57.         ke[v].pb(u);
  58.     }
  59.     dfs(1,-1);
  60.     for(int i=1;i<=n;i++){
  61.         update(1,1,n,tin[i],a[i]);
  62.     }
  63.     while(m--){
  64.         int type;
  65.         cin >> type;
  66.         if(type==1){
  67.             int x,val;
  68.             cin >> x >> val;
  69.             update(1,1,n,tin[x],val);
  70.         }
  71.         else{
  72.             int s;
  73.             cin >> s;
  74.             cout << get(1,1,n,tin[s],tout[s]) << el;
  75.         }
  76.     }
  77.     return 0;
  78. }
Success #stdin #stdout 0.01s 11608KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/YArdZJ
language:
C++14 (gcc 8.3)
created:
4 days 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!