これは典型かな…。
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の入り掛けと出がけに処理を行うのは常套テクだね。