Advertisement
Alexvans

Untitled

Jun 23rd, 2017
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.03 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define MAX 200005
  4. int t;
  5. int n,q;
  6. int v[MAX];
  7. int in[MAX];
  8. int bit[2*MAX];
  9. int fin[MAX];
  10. bool memo[MAX];
  11. int parity[MAX];
  12. vector<int>sons[MAX];
  13. void update(int i,int x){
  14.     while(i<2*MAX){
  15.         bit[i]+=x;
  16.         i+=(i&-i);
  17.     }
  18. }
  19. int query(int i){
  20.     int r=0;
  21.     while(i>0){
  22.         r+=bit[i];
  23.         i-=(i&-i);
  24.     }
  25.     return r;
  26. }
  27. void dfs(int nodo,int p){
  28.     if(memo[nodo])return;
  29.     memo[nodo]=true;
  30.     in[nodo]=++t;
  31.     parity[nodo]=p;
  32.     for(int i=0;i<sons[nodo].size();i++){
  33.         if(!memo[sons[nodo][i]]){
  34.             dfs(sons[nodo][i],-p);
  35.         }
  36.     }
  37.     fin[nodo]=++t;
  38. }
  39. int main (){
  40.     ios_base::sync_with_stdio(0);
  41.     cin.tie(0);
  42.  
  43.     cin>>n>>q;
  44.     for(int i=1;i<=n;i++){
  45.         cin>>v[i];
  46.     }
  47.     for(int i=1;i<n;i++){
  48.         int a,b;
  49.         cin>>a>>b;
  50.         sons[a].push_back(b);
  51.         sons[b].push_back(a);
  52.     }
  53.     dfs(1,1);
  54.     while(q--){
  55.         int op,a,b;
  56.         cin>>op;
  57.         if(op==1){
  58.             cin>>a>>b;
  59.             update(in[a],b*parity[a]);
  60.             update(fin[a]+1,-b*parity[a]);
  61.         }
  62.         else {
  63.             cin>>a;
  64.             cout << v[a]+query(in[a])*parity[a]<<"\n";
  65.         }
  66.     }
  67. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement