1 #include <iostream>  2 #include <cstdio>  3 #include <vector>  4 #include <algorithm>  5 #include <cstring>  6 using namespace std;  7 #define maxn 201000  8 #define lson l, m, rt<<1  9 #define rson m+1, r, rt<<1|1 10 #define ll long long 11 struct node 12 { 13     int cnt_o, cnt_e;  //分别记录奇层、偶层有几个儿子 14     int val; 15     int num, dep, next;   // num记录dfs序，dep 记录节点深度（这里节点1深度为1），next记录下一层的开头的节点。 16 }arr[maxn]; 17 int sgt_o[maxn<<2], sgt_e[maxn<<2]; 18 int lazy_o[maxn<<2], lazy_e[maxn<<2]; 19 vector<int> odd, even;     //分别记录在奇、偶层的原节点序号 20 int vis[maxn]; 21 int n, m; 22 int next[maxn<<1], first[maxn], v[maxn<<1], u[maxn<<1];  //邻接表 23 void init() 24 { 25     odd.clear(); even.clear(); 26     memset(first, -1, sizeof(first)); 27     memset(next, 0, sizeof(next)); 28     memset(vis, 0, sizeof(vis)); 29     for(int i = 1; i <= n; i++) { 30         scanf("%d", &arr[i].val); 31         arr[i].cnt_e = arr[i].cnt_o = arr[i].next = 0; 32     } 33     for(int i = 0; i < n-1; i++) {   //用邻接表存图 34         scanf("%d%d", &u[i], &v[i]); 35         next[i] = first[u[i]]; 36         first[u[i]] = i; 37         u[n+i] = v[i]; 38         v[n+i] = u[i]; 39         next[n+i] = first[v[i]]; 40         first[v[i]] = n+i; 41     } 42 } 43 struct child  //记录奇、偶的儿子数 44 { 45     int e, o; 46 }; 47 child dfs(int i, int &num1, int &num2, int dep)  //num1是奇层的dfs序，num2是偶层的dfs序 48 { 49     if(dep&1) odd.push_back(i); 50     else even.push_back(i); 51      52     if(dep&1) arr[i].num = num1++; 53     else arr[i].num = num2++; 54     arr[i].dep = dep; 55      56     vis[i] = 1; 57      58     int flag = 0; 59     if(dep&1) 60         for(int e = first[i]; e != -1; e = next[e]) { 61             if(!vis[v[e]]) { 62                 if(!flag) { 63                     arr[i].next = v[e]; flag = 1; 64                 } 65                 child x = dfs(v[e], num1, num2, dep+1); 66                 arr[i].cnt_e += x.e; 67                 arr[i].cnt_o += x.o; 68             } 69         } 70     else { 71         for(int e = first[i]; e != -1; e = next[e]) { 72             if(!vis[v[e]]) { 73                 if(!flag) { 74                     arr[i].next = v[e]; flag = 1; 75                 } 76                 child x = dfs(v[e], num1, num2, dep+1); 77                 arr[i].cnt_e += x.e; 78                 arr[i].cnt_o += x.o; 79             } 80         } 81     } 82     child xx; xx.o = arr[i].cnt_o; xx.e = arr[i].cnt_e; 83     if(dep&1) xx.o++; else xx.e++; 84     return xx; 85 } 86  87 void build_o(int l, int r, int rt)   //建奇层节点的线段树 88 { 89     sgt_o[rt] = 0; 90     if(l == r) { 91         int x = odd[l-1]; 92         sgt_o[rt] = arr[x].val; 93         return; 94     } 95     int m = (r+l)>>1; 96     build_o(lson); 97     build_o(rson); 98 } 99 void build_e(int l, int r, int rt)  //建偶层节点的线段树100 {101     sgt_e[rt] = 0;102     if(l == r) {103         int x = even[l-1];104         sgt_e[rt] = arr[x].val;105         return;106     }107     int m = (l+r)>>1;108     build_e(lson);109     build_e(rson);110 }111 void push_down(int rt, int x, int *lazy)112 {113     if(lazy[rt] != 0) {114         lazy[rt<<1] += lazy[rt];115         lazy[rt<<1|1] += lazy[rt];116         lazy[rt] = 0;117     }118 }119 void change(int l, int r, int rt, int L, int R, int del, int *sgt, int *lazy)120 {121     if(L <= l && r <= R)122     {123         lazy[rt] += del;124         return;125     }126     int x = (r-l+1);127     push_down(rt, x, lazy);128     int m = (l+r)>>1;129     if(L <= m) change(lson, L, R, del, sgt, lazy);130     if(m < R) change(rson, L, R, del, sgt, lazy);131 }132 int query(int l, int r, int rt, int pos, int *sgt, int *lazy)133 {134     if(l == r) {135         sgt[rt] += lazy[rt];136         lazy[rt] = 0;137         return sgt[rt];138     }139     int m = (l+r)>>1;140     push_down(rt, r-l+1, lazy);141     if(pos <= m) return query(lson, pos, sgt, lazy);142     return query(rson, pos, sgt, lazy);143 }144 void work()145 {146     init();147     int num1 = 1, num2 = 1;148     dfs(1, num1, num2, 1);149     int n1 = odd.size(), n2 = even.size(); 150     if(n1 > 0)build_o(1, n1, 1); 151     if(n2 > 0)build_e(1, n2, 1);152     while(m--) {153         int a, b; scanf("%d%d", &a, &b);154         if(a == 1) {155             int c; scanf("%d", &c);156             if(arr[b].dep&1) {157                 change(1, n1, 1, arr[b].num, arr[b].num+arr[b].cnt_o, c, sgt_o, lazy_o);158                 if(arr[b].next != 0) {159                     int ne = arr[b].next;160                     change(1, n2, 1, arr[ne].num, arr[ne].num+arr[b].cnt_e-1, -c, sgt_e, lazy_e);161                 }162             }163             else {164                 change(1, n2, 1, arr[b].num, arr[b].num+arr[b].cnt_e, c, sgt_e, lazy_e);165                 if(arr[b].next != 0) {166                     int ne = arr[b].next; 167                     change(1, n1, 1, arr[ne].num, arr[ne].num+arr[b].cnt_o-1, -c, sgt_o, lazy_o);168                 }169             }170         }171         else {172             int res;173             if(arr[b].dep&1) {174                 res = query(1, n1, 1, arr[b].num, sgt_o, lazy_o);175             }176             else {177                 res = query(1, n2, 1, arr[b].num, sgt_e, lazy_e);178             }179             printf("%d\n", res);180         }181     }182 }183 int main()184 {185     while(scanf("%d%d", &n, &m) != EOF) work();186     return 0;187 }