Educational Codeforces Round 54 E. Vasya and a Tree(树上差分数组）

https://codeforces.com/contest/1076/problem/E

题意

给一棵树(n<=3e5),m(3e5)次查询,每次查询u,d,x,表示在u的子树中，给距离u<=d,的每个点权值加上x，最后输出每个点的权值

思路

每个点的权值和子节点的修改无关
利用dfs的性质，可以用差分数组顺着每一条路径，在每一个点，维护前缀和（计算出当前点的答案），遍历对当前点的询问维护后面点的权值（用差分标记）
因为到u点距离相等的点，深度一定相等，加上dfs先往深处搜的性质（dfs每搜到一个叶子，实际上对应着一条唯一（深度相等的点只有一个）的路径），所以差分数组只需要用深度做下标即可，返回的时候需要清空当前节点对后面节点的差分修改

#include<bits/stdc++.h>

#define ll long long

#define M 300005

#define pb push_back

using namespace std;

struct N{

    int d;ll v;

};

ll sum[M],d[M];

vector<N>p[M];

vector<int>g[M];

int n,i,u,v,m,D;

void dfs(int u,int fa,int dep){

    sum[u]=sum[fa]+d[dep];

    for(int i=0;i<p[u].size();i++){

        N x=p[u][i];

        sum[u]+=x.v;

        if(dep+x.d+1<n)d[dep+x.d+1]-=x.v;

    }

    for(int i=0;i<g[u].size();i++){

        int v=g[u][i];if(v==fa)continue;

        dfs(v,u,dep+1);

    }

    for(int i=0;i<p[u].size();i++){

        N x=p[u][i];

        if(dep+x.d+1<n)d[dep+x.d+1]+=x.v;

    }

}

int main(){

    cin>>n;

    for(i=0;i<n-1;i++){

        scanf("%d%d",&u,&v);

        g[u].pb(v);g[v].pb(u);

    }

    cin>>m;

    while(m--){

        scanf("%d%d%d",&u,&D,&v);

        p[u].pb(N{D,v});

    }

    dfs(1,0,0);

    for(i=1;i<=n;i++)printf("%lld ",sum[i]);

}

巴特西

Educational Codeforces Round 54 E. Vasya and a Tree(树上差分数组）

题意

思路

最新文章

热门文章