Vasya and a Tree CodeForces - 1076E

很好的思维

转化为对树上的深度差分

回朔的思想

对查询离线

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<string>

#include<queue>

#include<map>

#include<set>

#include<list>

#include<ctime>

#include<ctype.h>

#include<bitset>

#include<algorithm>

#include<numeric> //accumulate

#define endl "\n"

#define fi first

#define se second

#define FOR(i,s,t) for(int i=(s);i<=(t);++i)

#define mem(a,b) memset(a,b,sizeof(a))

using namespace std;

const int maxn=+;

int n;

vector<int> g[maxn];

vector<pair<int,int> > q[maxn];

long long add[maxn];

long long ans[maxn];

void dfs(int u,int pa,int dep,long long sum)

{

    for(auto i:q[u])

    {

        int l=dep,r=dep+i.fi+;

        add[l]+=i.se;

        if(r<=n)

            add[r]-=i.se;

    }

    sum+=add[dep];

    ans[u]=sum;

    for(auto i:g[u])

    {

        if(i==pa)

            continue;

        dfs(i,u,dep+,sum);

    }

    for(auto i:q[u])

    {

        int l=dep,r=dep+i.fi+;

        add[l]-=i.se;

        if(r<=n)

            add[r]+=i.se;

    }

}

int main()

{

    cin.tie();

    cout.tie();

    ios_base::sync_with_stdio(false);

    //freopen("in.txt","r",stdin);

    //freopen("out.txt","w",stdout);

    cin>>n;

    for(int i=;i<n;i++)

    {

        int x,y;

        cin>>x>>y;

        g[x].push_back(y);

        g[y].push_back(x);

    }

    int m;

    cin>>m;

    for(int i=;i<m;i++)

    {

        int v,d,x;

        cin>>v>>d>>x;

        q[v].push_back({d,x});

    }

    dfs(,,,0ll);

    for(int i=;i<=n;i++)

        cout<<ans[i]<<' ';

}

/*

void read()

{

    char c = getchar();

    int x = 0;

    for (; (c < 48 || c>57); c = getchar());

    for (; c > 47 && c < 58; c = getchar())

    {

        x = (x << 1) + (x << 3) + c - 48;

    }

    return x;

}

*/