Educational Codeforces Round 54 E. Vasya and a Tree

树上前缀和

#include <bits/stdc++.h>
#define mem(ar,num) memset(ar,num,sizeof(ar))
#define me(ar) memset(ar,0,sizeof(ar))
#define lowbit(x) (x&(-x))
#define Pb push_back
#define FI first
#define SE second
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define IOS ios::sync_with_stdio(false)
#define DEBUG cout<<endl<<"DEBUG"<<endl; 
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int    prime = 999983;
const int    INF = 0x7FFFFFFF;
const LL     INFF =0x7FFFFFFFFFFFFFFF;
const double pi = acos(-1.0);
const double inf = 1e18;
const double eps = 1e-6;
const LL     mod = 1e9 + 7;
LL qpow(LL a,LL b){LL s=1;while(b>0){if(b&1)s=s*a%mod;a=a*a%mod;b>>=1;}return s;}
LL gcd(LL a,LL b) {return b?gcd(b,a%b):a;}
int dr[2][4] = {1,-1,0,0,0,0,-1,1};
typedef pair<LL,LL> P;
const int maxn = 3e5+100;
LL add[maxn];
LL res[maxn];
vector<LL> G[maxn];
vector<P> command[maxn];
int n,m;
void dfs(int node,int h,int fa,LL sum){
    for(auto c: command[node])
    {
        int l = h,r = l + c.first;
        add[l] += c.second;
        if(r+1 <= n)
            add[r+1] -= c.second;
    }
    sum += add[h];
    res[node] = sum;
    for(auto c: G[node]){
        if(c == fa) continue;
        dfs(c,h+1,node,sum);
    }
    sum -= add[h];
    for(auto c: command[node])
    {
        int l = h,r = l + c.first;
        add[l] -= c.second;
        if(r+1 <= n)
            add[r+1] += c.second;
    }
}
int main(void)
{  
    cin>>n;
    for(int i = 0,v,u;i < n-1; ++i){
        scanf("%d%d",&v,&u);
        G[v].Pb(u);
        G[u].Pb(v);
    }
    cin>>m;
    for(int i = 0,v,h,x;i < m; ++i){
        scanf("%d%d%d",&v,&h,&x);
        command[v].Pb(P(h,x));
    }
    dfs(1,0,-1,0);

    for(int i = 1;i <= n; ++i)
        printf("%lld%c",res[i]," \n"[i==n]);
        

    return 0;
}

树状数组

分析

// 假设我们通过dfs序进入u节点，我们把它对于子节点的贡献都加上，相当于区间修改，树状数组的节点是深度
// 出去这个节点的时候把u把u节点的影响减去，因为u节点对于其它的没有贡献
// 树状数组是前缀和，所以我们区间修改的时候 修改的是一段区间,[l,l+h],我们其实可以当成是修改[1,l+h];,这样也不会对[l+h+1,n] 的有影响
// 所以可以把深度都取反

#include <bits/stdc++.h>
#define mem(ar,num) memset(ar,num,sizeof(ar))
#define me(ar) memset(ar,0,sizeof(ar))
#define lowbit(x) (x&(-x))
#define Pb push_back
#define FI first
#define SE second
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define IOS ios::sync_with_stdio(false)
#define DEBUG cout<<endl<<"DEBUG"<<endl; 
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int    prime = 999983;
const int    INF = 0x7FFFFFFF;
const LL     INFF =0x7FFFFFFFFFFFFFFF;
const double pi = acos(-1.0);
const double inf = 1e18;
const double eps = 1e-6;
const LL     mod = 1e9 + 7;
LL qpow(LL a,LL b){LL s=1;while(b>0){if(b&1)s=s*a%mod;a=a*a%mod;b>>=1;}return s;}
LL gcd(LL a,LL b) {return b?gcd(b,a%b):a;}
int dr[2][4] = {1,-1,0,0,0,0,-1,1};
typedef pair<int,int> Pii;
typedef pair<LL,LL> PLL;
const int maxn = 3e5+100;
LL tree[maxn];// 线段树

void Add(int x,int p){
    x++;
    while(x < maxn){
        tree[x] += p;
        x += lowbit(x);
    }
}
LL Sum(int x){
    LL ans = 0;
    x++;
    while(x > 0){
        ans += tree[x];
        x -= lowbit(x);
    }
    return ans;
}
LL depth[maxn];
int id[maxn];// id[i] 代表节点i的dfs序
int vs[maxn];// vs[i] 代表dfs序为i的节点编号
int ed[maxn];// 打表子树中最大的dfs序

LL ans[maxn];
std::vector<int> G[maxn];
std::vector<PLL> Q[maxn];
int k = 0;
void dfs(int node,int fa){
    id[node] = ++k;
    vs[k] = node;
    // depth[node] = d;/
    for(auto c: G[node]){
        if(c == fa) continue;
        depth[c] = depth[node]+1;
        dfs(c,node);
    }
    ed[node] = k;
}
int main(void)
{
    int n;
    cin>>n;
    for(int i = 2;i <= n; ++i){
        int u,v;
        scanf("%d%d",&u,&v);
        G[u].Pb(v);
        G[v].Pb(u);
    }
    depth[1] = 1;
    dfs(1,-1);
    int m;
    cin>>m;
    for(int i = 1;i <= m; ++i){
        LL u,d,v;
        scanf("%lld%lld%lld",&u,&d,&v);
        Q[id[u]].Pb(PLL(min(depth[u]+d,(LL)n),v));
        Q[ed[u]+1].Pb(PLL(min(depth[u]+d,(LL)n),-v));
    }
    for(int i= 1;i <= n; ++i){
        for(auto c: Q[i]){
            Add(n-c.first,c.second);
        }
        ans[vs[i]] = Sum(n-depth[vs[i]]);
    }
    for(int i = 1;i <= n; ++i)
        cout<<ans[i]<<" ";
    

   return 0;
}