[CF][补题][线段树][树] codeforces 1076E Vasya and a Tree

这个题自己当时主要还是思维限制，只想着怎么能有类似于dfs序线段树那种操作，或者是就某个点对他的子树做一个什么类似于线段树的打标记处理。。但是感觉太复杂了，没搞出来，而且也没有把可以离线这个点利用起来，还是too young

正解是在dfs过程中维护一个线段树，这棵树的下标是代表了当前dfs到的深度（而非节点），看到这儿就感觉是个很妙的操作，这样的话只需要每次进入到一个节点的时候把对应的属于该节点的所有的操作（这个需要离线处理，把对应的操作存用个vector存起来就可以了）都处理一遍，也就是把对应的所有的区间上的数值加上，dfs离开的时候把对应的区间上的数值减去，回滚一下，就可以保证在dfs过程中就把所有的操作处理完了。

 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <set>
#include <map>
#include <string>
#include<cmath>
#include<queue>

using namespace std;

typedef long long LL;
const int maxn = 6e5 + 5;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;

LL sum[maxn<<2],add[maxn<<2];
int pl,pr,x;

void maintain(int o,int l,int r)
{
    sum[o]=add[o]*(r-l+1)+sum[o<<1]+sum[o<<1|1];
}

void pushdown(int o)
{
    add[o<<1]+=add[o],add[o<<1|1]+=add[o];add[o]=0;
}

void update(int o,int l,int r)
{
    if(pl<=l&&r<=pr)
    {
        add[o]+=x;
    }
    else
    {
        int m=(l+r)>>1;
        pushdown(o);
        if(pl<=m)update(o<<1,l,m);else maintain(o<<1,l,m);
        if(m<pr)update(o<<1|1,m+1,r);else maintain(o<<1|1,m+1,r);
    }
    maintain(o,l,r);
}

int qp;
LL pans;
void query(int o,int l,int r)
{
    maintain(o,l,r);
    if(l==r)
    {
        pans=sum[o];return ;
    }
    else
    {
        int m=(l+r)>>1;
        pushdown(o);
        if(qp<=m)query(o<<1,l,m);
        else query(o<<1|1,m+1,r);
    }
}

vector<int> G[maxn];
vector<pair<int,int> > cmds[maxn];
LL ans[maxn];

int cd,n;
void dfs(int s,int p,int dpt)
{
    int len=cmds[s].size();
    for(int i=0;i<len;i++)
    {
        cd=cmds[s][i].first,x=cmds[s][i].second;
        pl=dpt,pr=dpt+cd;
        update(1,1,n);
    }
    qp=dpt;query(1,1,n);//注意是下标都是表示的深度
    ans[s]=pans;
    len=G[s].size();
    for(int i=0;i<len;i++)
    {
        if(G[s][i]==p)continue;
        dfs(G[s][i],s,dpt+1);
    }
    //rollback
    len=cmds[s].size();
    for(int i=0;i<len;i++)
    {
        cd=cmds[s][i].first,x=-cmds[s][i].second;
        pl=dpt,pr=dpt+cd;
        update(1,1,n);
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int m,x,y,v,d;
    cin>>n;
    for (int i=1;i<n;i++)
    {
        cin>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    cin>>m;
    for (int i=1;i<=m;i++)
    {
        cin>>v>>d>>x;
        cmds[v].push_back(make_pair(d,x));
    }

    dfs(1,0,1);
    for(int i=1;i<=n;i++)
        cout<<ans[i]<<" ";
    return 0;
}