Codeforces #225(383 Div1) C. Propagating tree
問題
1番のノードが根であるような木が与えられる。各ノードは値a[i]をもっている。
木に対して次のクエリを行うことができる。
1 x val : x番の頂点にvalを足す。x番の直接の子に-valを足す。x番の頂点の2代目の子孫にvalを足す3代目の頂点に-valを足す……を葉までやる。
2 x : 頂点xに書かれた数字を出力する。
制約条件
n, クエリの個数≦ 2*10^5
方針
Euler tour + binary indexed treeふたつ。
奇数の深さ用のBITと偶数の深さ用のBIT二つをもってやり、
自分と同じパリティのBITの値は足して、違うパリティのBITの値は引けばよい。
Euler tourを完全に忘れていたのでHL-分解で無理矢理解いた。
最近Euler tourを忘れることが多い。
ソースコード
void size_rec(int, int); void heavy_light_rec(int, int, int); const int MX = 200010; struct S{ int n; vi bit1, bit2; S(int sz):n(sz + 2){ bit1.resize(n); bit2.resize(n); } inline void add(int type, int i, int x){ vi &bit = type ? bit2 : bit1; for(i++; i < n; i += i & -i) bit[i] += x; } inline int sum(int type, int i){ vi &bit = type ? bit2 : bit1; int res = 0; for(i++; i; i -= i & -i) res += bit[i]; return res; } }; S *data[MX]; int bkt_sz; int bkt_root[MX]; int n, q; int sz[MX], a[MX]; int parent[MX]; int depth[MX]; int which[MX]; int val[MX]; vector<vi> e; int main(){ scanf("%d%d", &n, &q); e.resize(n); rep(i, n) scanf("%d", a + i); rep(i, n - 1){ int a, b; scanf("%d%d", &a, &b); a--; b--; e[a].pb(b); e[b].pb(a); } memset(which, -1, sizeof(which)); size_rec(0, 0); heavy_light_rec(0, 0, -1); while(q--){ int t, b; scanf("%d%d", &t, &b); b--; if(t == 1){ int x; scanf("%d", &x); int bkt = which[b]; if(bkt < 0) val[b] += x; else{ int pos = depth[b] - depth[bkt_root[bkt]]; data[bkt]->add(pos % 2, pos, x); } } else{ int ans = a[b]; int flip = 1; while(1){ int bkt = which[b], pos; if(bkt < 0) ans += flip * val[b]; else{ pos = depth[b] - depth[bkt_root[bkt]]; ans += flip * data[bkt]->sum(pos % 2, pos); ans -= flip * data[bkt]->sum(1 - pos % 2, pos - 1); } if(b == 0 || bkt >= 0 && bkt_root[bkt] == 0) break; int pd = depth[b]; if(bkt < 0) b = parent[b], flip *= -1; else b = parent[bkt_root[bkt]], flip *= pos % 2 ? 1 : -1; } printf("%d\n", ans); } } return 0; } inline void size_rec(int c, int p){ sz[c] = 1; depth[c] = c == p ? 0 : depth[p] + 1; parent[c] = p; rep(i, e[c].size()) if(e[c][i] != p){ size_rec(e[c][i], c); sz[c] += sz[e[c][i]]; } } inline void heavy_light_rec(int c, int p, int root){ bool found = 0; rep(i, e[c].size()){ int to = e[c][i]; if(to == p) continue; if(2 * sz[to] >= sz[c]){ heavy_light_rec(to, c, root < 0 ? c : root); found = 1; } else heavy_light_rec(to, c, -1); } if(!found && root >= 0){ int size = depth[c] - depth[root] + 1; bkt_root[bkt_sz] = root; data[bkt_sz] = new S(size); for(int v = c; ; v = parent[v]){ which[v] = bkt_sz; if(v == root) break; } bkt_sz++; } }