codeforces 1076E Vasya and a Tree 树上差分-蒲公英云

codeforces 1076E Vasya and a Tree 树上差分

题意：给你一棵1为根节点的树，初始每个节点权值为0，有m次操作，每次操作 v d x，表示将以v为根的子树，深度不超过d的所有节点加上x。

思路：dfs的性质+差分思想，dfs记录以该节点为起点的所有操作影响的深度范围，在从该节点回溯时再把影响减去，因为dfs时只会在子树中遍历，所以用这种方法就把影响限制在了子树的规定深度中。

参考博客：https://www.cnblogs.com/pkgunboat/p/9955562.html

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e6+10;
int n,m,vs[N],d[N],w[N];
ll ans[N];
vector<int> e[N];
struct nd{
    int d,x;
};
vector<nd> g[N];
void dfs(int u,ll val) {
    val+=w[d[u]];
    for(int i=0;i<g[u].size();i++) {
        int dep=min(n,d[u]+g[u][i].d);
        ///差分
        w[dep+1]-=g[u][i].x;
        val+=g[u][i].x;
    }
    ans[u]=val;
    for(int i=0;i<e[u].size();i++) {
        int v=e[u][i];
        if(!d[v]) {
            d[v]=d[u]+1;
            dfs(v,val);
        }
    }
    ///回溯把影响减去
    for(int i=0;i<g[u].size();i++) {
        int dep=min(n,d[u]+g[u][i].d);
        w[dep+1]+=g[u][i].x;
    }
}
int main() {
    scanf("%d",&n);
    for(int i=1;i<n;i++) {
        int x,y;
        scanf("%d%d",&x,&y);
        e[x].push_back(y);
        e[y].push_back(x);
    }
    scanf("%d",&m);
    while(m--) {
        int v,d,x;
        scanf("%d%d%d",&v,&d,&x);
        g[v].push_back({d,x});
    }
    d[1]=1;
    dfs(1,0);
    for(int i=1;i<=n;i++) printf("%lld ",ans[i]);
    return 0;
}