Codeforces #225 Div1. C. Propagating tree

最後の一手のとり方がわからなかった問題。
http://codeforces.com/contest/383/problem/C

問題

１番の点を根とする木構造を成すグラフが与えられる。また、初期状態として各点iには整数A[i]が与えられている。
ここで、以下の２種類のクエリをM個対応せよ。

• 1 x v : x番の点の整数にvを加算し、x番の子の点に-vを加算する。この加算は子に伝搬し、x番の子の子には-(-v)を加算し、以後葉までこの符号を変えながらの加算は伝搬する。
• 2 x : x番の点の整数を答えよ。

解法

１番のクエリでは、ある点のsubtreeに対し何らかの数字を増減するので、Euler tourとFenwickTreeを使うところまではすんなり想像がついた。
問題は子をたどるごとに増減する数値の符号が反転することである。

当然ながら、各点iの深さをD[i]とすると、1番のクエリでx番のsubtreeに含まれるy番の点には、D[x]とD[y]の偶奇の違いにより、vの符号が決定する。

そこで、２種類のFenwickTreeを作ることにする。
１番のクエリを行う場合、D[x]の偶奇に対応したFenwickTreeに対して、そのsubtreeの各点に数字を加える。この際は符号の反転は無視してよい。

２番のクエリを行う際に工夫が必要で、D[x]が偶数なら、偶数番に対応するクエリ総和のFenwickTreeの値から奇数番に対応するクエリ総和のFenwickTreeの値を引き、A[x]を足して答えればよい。
D[x]が奇数ならその逆で、奇数番に対応するクエリ総和のFenwickTreeの値から偶数番に対応するクエリ総和のFenwickTreeの値を引き、A[x]を足して答えればよい。

このように、２番のクエリの段階で符号反転の処理をまとめて行えばよい。
１番も２番もFenwickTreeの更新と参照でO(logN)で処理できるので、全体でO(M logN)で処理できる。

int N,M;
int A[200100];
vector<int> E[200100];
int L[200100],R[200100],D[200100];
int id;

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];

	V total(int entry) {
		V s=0;
		entry++;
		while(entry>0) s+=bit[entry-1], entry -= entry & -entry;
		return s;
	}
	void update(int entry, V val) {
		entry++;
		while(entry <= (1<<ME)) bit[entry-1] += val, entry += entry & -entry;
	}
};
BIT<int,20> bt[2];

void dfs(int cur,int pre) {
	int i,t=-1;
	L[cur]=++id;
	FOR(i,E[cur].size()) {
		int tar=E[cur][i];
		if(tar==pre) t=i;
		else D[tar]=D[cur]+1, dfs(tar,cur);
	}
	R[cur]=id;
}

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>M;
	FOR(i,N) cin>>A[i];
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	dfs(0,-1);
	
	FOR(i,M) {
		cin>>x;
		if(x==1) {
			cin>>x>>y;
			
			bt[D[x-1]&1].update(L[x-1],y);
			bt[D[x-1]&1].update(R[x-1]+1,-y);
		}
		else {
			cin>>x;
			
			y = bt[0].total(L[x-1]) - bt[1].total(L[x-1]);
			if(D[x-1]&1) y=-y;
			_P("%d\n", A[x-1] + y);
		}
	}
}

まとめ

終わってしまえばあっさり。本番中に思いつきたいなあ。