题目链接:https://nanti.jisuanke.com/t/A1998
题目大意:给你一棵树,有两个操作:
1 L X:树的L深度的节点权值+=X
2 X:查询X的子树的权值和
图片说明
图片说明

#include <bits/stdc++.h>
#define LL long long
using namespace std;

LL s[200005], n=200005;
void add(LL x,LL z) {for (LL i=x;i<=n;i+=(i&(-i))) s[i]+=z;}
LL ask(LL x) {LL ans=0;for (LL i=x;i>0;i-=(i&(-i))) ans+=s[i];return ans;}
LL ask(LL x, LL y){return ask(y)-ask(x-1);}

vector<LL> G[100005], son[100005];
LL father[100005], d[200005], dfn[200005], out[200005], lza[200005], T=0;
void DFS(LL u, LL fa, LL deep){
    father[u]=fa; dfn[u]=++T; d[u]=deep;
    son[deep].push_back(u);
    for(auto x: G[u]){
        if(x!=fa){
            DFS(x, u, deep+1);
        }
    }
    out[u]=T;
}

map<LL, LL> M[100005];
int main(){
    LL n, q, x, y; scanf("%lld%lld", &n, &q);
    for(LL i=1; i<n; i++){
        scanf("%lld%lld", &x, &y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    DFS(1, 0, 0);
    LL len=sqrt(n/(log(n)+1));
    for(LL i=1; i<=n ;i++){
        if(son[d[i]].size()>len){//如果这层节点数>len。用3维护
            LL u=i, deep=d[u];
            while(u){
                M[u][deep]++;
                u=father[u];
            }
        }
    }
    while(q--){
        LL k; scanf("%lld", &k);
        if(k==1){
            scanf("%lld%lld", &x, &y);
            if(son[x].size()<=len){//用1维护修改
                for(auto pos: son[x]){
                    add(dfn[pos], y);
                }
            }
            else{
                lza[x]+=y;//用3维护修改
            }
        }
        else{
            LL ans=0;
            scanf("%lld", &x);
            for(auto pos: M[x]){//用3维护查询
                ans+=pos.second*lza[pos.first];
            }
            ans+=ask(dfn[x], out[x]);//用1维护查询
            printf("%lld\n", ans);
        }
    }

    return 0;
}