Codeforces ECR #054 : E. Vasya and a Tree

これは典型かな…。
http://codeforces.com/contest/1076/problem/E

問題

根付き木が与えられる。
各頂点には整数値が設定可能で、初期状態では0である。
以下のクエリを順次処理し、最終的な各頂点の設定値を答えよ。

• クエリは頂点v、深さd、値xからなる。vのSubTreeのうちvからの距離がd以下の頂点の設定値にxを加算する。

解法

深さ方向に累積和を取りながら、DFSで頂点vに出入りする際累積和の配列にxを加減算していこう。

int N,M;
vector<int> E[301010];
vector<pair<int,int>> ev[303030];
ll add[303030];
ll tot=0;
ll ret[303030];

void dfs(int cur,int pre,int dep) {
	FORR(e,ev[cur]) {
		add[dep]+=e.second;
		if(dep+e.first<=303000) add[dep+e.first+1]-=e.second;
	}
	
	tot+=add[dep];
	ret[cur]=tot;
	FORR(e,E[cur]) if(e!=pre) dfs(e,cur,dep+1);
	
	tot-=add[dep];
	FORR(e,ev[cur]) {
		add[dep]-=e.second;
		if(dep+e.first<=303000) add[dep+e.first+1]+=e.second;
	}
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d",&N);
	FOR(i,N-1) {
		scanf("%d%d",&x,&y);
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	scanf("%d",&M);
	FOR(i,M) {
		scanf("%d%d%d",&x,&y,&r);
		ev[x-1].push_back({y,r});
	}
	
	dfs(0,-1,0);
	FOR(i,N) cout<<ret[i]<<" ";
	
	
}

まとめ

SubTree内の頂点に一括で処理するとき、DFSの入り掛けと出がけに処理を行うのは常套テクだね。