Educational Codeforces Round 54 (Rated for Div. 2)(E. Vasya and a Tree)

链接：http://codeforces.com/contest/1076/problem/E
思路：学到了一种新姿势啊，首先来一次dfs或者bfs给树标上深度，然后来dfs，每次到一个结点查询上面是否有需要更新的，然后用深度代表树状数组的下标，在dep[u]上加上权值，在dep[u]+d+1上减去一个权值，这样对于范围外的点用树状数组求和时就可以刚好抵消使得答案不变，而里面的点就可以得到更新后的答案，然后当遍历完回溯时把加上和扣除的权值还原即可。
代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,ll> P;
const int maxn = 3e5+100;
ll c[maxn];
ll res[maxn];
int dep[maxn];
vector<int> G[maxn];
int n,m;

vector<P> ans[maxn];

int lowbit(int x){
    return x&(-x);
}

void add(int x,ll d){
    while(x<maxn){
        c[x]+=d;
        x+=lowbit(x);
    }
}

ll query(int x){
    ll res = 0;
    while(x){
        res+=c[x];
        x-=lowbit(x);
    }
    return res;
}

void dfs(int u,int f){
    for(int i=0;i<G[u].size();i++){
        int v = G[u][i];
        if(v==f)continue;
        dep[v] = dep[u] + 1;
        dfs(v,u);
    }
}

void work(int u,int f){
    for(int i=0;i<ans[u].size();i++){
        int d = ans[u][i].first;
        int w = ans[u][i].second;
        if(d>n)d = n;
  //差分，用dfs当一个偏序，然后在此偏序上用树状数组维护前缀和
      add(dep[u],w);
        add(dep[u]+d+1,-w); 
    }
    res[u] = query(dep[u]);
    for(int i=0;i<G[u].size();i++){
        int v = G[u][i];
        if(v==f)continue;
        work(v,u);
    }
    for(int i=0;i<ans[u].size();i++){
        int d = ans[u][i].first;
        int w = ans[u][i].second;
        if(d>n)d = n;
  //还原
        add(dep[u],-w);
        add(dep[u]+d+1,w); 
    }
}

int main(){
    scanf("%d",&n);
    for(int i=0;i<n-1;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    scanf("%d",&m);
    for(int i=0;i<m;i++){
        int v,d;
        ll x;
        scanf("%d%d%lld",&v,&d,&x);
        ans[v].push_back(P{d,x});
    }
    dep[1] = 1;
    dfs(1,-1);
    work(1,-1);
    for(int i=1;i<=n;i++)printf("%lld ",res[i]);
    printf("\n");
    return 0;
}