题目链接：http://codeforces.com/problemset/problem/384/E
大意：给定一颗n节点的树，一共有两种操作：1. 给节点x加val，同时，它的所有孩子要减val，孙子加val，孙子的孩子减val，以此类推。2.查询节点x的值。
思路：对于某个节点来说，如果某节点的深度的奇偶性和该节点相同，则他们修改时符号也相同（要么都加要么都减），若奇偶性不同，则修改时符号也不同。因此，我们按照节点的奇偶性建立两棵线段树。修改时，分别修改在同一棵树上的节点和另一棵树上的节点即可。
#include<cstdio> #include<cstring> #include<string> #include<cctype> #include<iostream> #include<set> #include<map> #include<cmath> #include<sstream> #include<vector> #include<stack> #include<queue> #include<algorithm> #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define fin(a) freopen("a.txt","r",stdin) #define fout(a) freopen("a.txt","w",stdout) typedef long long LL; using namespace std; typedef pair<int, int> P; const int INF = 1e8 + 10; const int maxn = 2e5 + 10; int val[maxn]; vector<int> G[maxn]; int L[maxn], R[maxn]; int cnt; bool vis[maxn]; int depth[maxn]; void dfs(int u, int d) { L[u] = ++cnt; vis[u] = 1; depth[u] = (d & 1); for(int i = 0; i < G[u].size(); i++) { int v = G[u][i]; if(vis[v]) continue; dfs(v, d+1); } R[u] = cnt; } struct Tree { int sum[maxn<<2], add[maxn<<2]; void PushDown(int rt, int m) { if(add[rt]) { add[rt<<1] += add[rt]; add[rt<<1|1] += add[rt]; sum[rt<<1] += add[rt] * (m - (m >> 1)); sum[rt<<1|1] += add[rt] * (m >> 1); add[rt] = 0; } } void build(int l, int r, int rt) { if(l == r) { sum[rt] = add[rt] = 0; } else { int m = (l + r) >> 1; build(lson); build(rson); sum[rt] = add[rt] = 0; } } void update(int ql, int qr, int x, int l, int r, int rt) { if(ql <= l && r <= qr) { add[rt] += x; sum[rt] += (r-l+1)*x; } else { PushDown(rt, r-l+1); int m = (l + r) >> 1; if(ql <= m) update(ql, qr, x, lson); if(m < qr) update(ql, qr, x, rson); sum[rt] = sum[rt<<1] + sum[rt<<1|1]; } } int query(int p, int l, int r, int rt) { if(l == r) return sum[rt]; PushDown(rt, r-l+1); int m = (l + r) >> 1; if(p <= m) return query(p, lson); return query(p, rson); } }tree[2]; int main() { int n, q; scanf("%d%d", &n, &q); for(int i = 1; i <= n; i++) { scanf("%d", &val[i]); G[i].clear(); } for(int i = 1; i <= n-1; i++) { int u, v; scanf("%d%d", &u, &v); G[u].push_back(v); G[v].push_back(u); } memset(vis, false, sizeof vis); dfs(1, 0); tree[0].build(1, cnt, 1); tree[1].build(1, cnt, 1); for(int i = 1; i <= n; i++) tree[depth[i]].update(L[i], L[i], val[i], 1, cnt, 1); while(q--) { int x, y, p; scanf("%d", &p); if(p == 1) { scanf("%d%d", &x, &y); int l = L[x], r = R[x]; tree[depth[x]].update(l, r, y, 1, cnt, 1); tree[depth[x]^1].update(l, r, -y, 1, cnt, 1); } else { scanf("%d", &x); int p = L[x]; printf("%d\n", tree[depth[x]].query(p, 1, cnt, 1)); } } return 0; }