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++;
	}
}