codeforces 1076E Vasya and a Tree 树上差分

谁借莪１个温暖的怀抱￠ 2022-01-22 12:41 180阅读 0赞

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

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

## 参考博客：[https://www.cnblogs.com/pkgunboat/p/9955562.html][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;
    }

[https_www.cnblogs.com_pkgunboat_p_9955562.html]: https://www.cnblogs.com/pkgunboat/p/9955562.html