题意

给定一棵无边权的树，最多只有一个点度数超过2，有两种操作

1）（0 u x d）将距离u节点d距离之内的节点的值加上x

2）（1 u）询问u节点的值

n<=100000,q<=100000

题解

只有一个点度数超过2，那么把它当根，整棵树的形态就是从根开始向下延伸许多链，

将距离u节点d距离之内的节点的值加上x，放在u的子树内（应该叫子链吧？）就是区间修改，可以用线段树或树状数组维护这每一条链，

如果距离u节点d距离之内的节点包括根的话，就要先把u到根的路径加上x，然后把距离根节点d - dis(u,root) 距离之内的其它节点的值加上x，很麻烦

此时需要单独拿一个数据结构维护从根开始延伸的贡献，下标为 i 的数记录深度为 i 的点共同增加过的x之和，于是 “ 把距离根节点d - dis(u,root) 距离之内的其它节点的值加上x ” 就可以在 [1, d - dis(u,root) +1] 上增加x（设根的深度为1），然后在u所在的链上去掉重复的部分

当我们访问一个点的权值时，除了要加上它所在的链上的权值，还要加上对应深度的共同权值。

根要特判。

CODE

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<algorithm>
#define MAXN 100005
#define ENDL putchar('\n')
#define LL long long
#define DB double
#define lowbit(x) ((-x)&(x))
//#define int LL
//#pragma GCC optimize(2)
using namespace std;
inline LL read() {
    LL f = 1,x = 0;char s = getchar();
    while(s < '0' || s > '9') {if(s == '-')f = -1;s = getchar();}
    while(s >= '0' && s <= '9') {x = x * 10 + (s - '0');s = getchar();}
    return x * f;
}
const int jzm = 1000000007;
int n,m,i,j,s,o,k,root;
int ind[MAXN];
vector<int> g[MAXN];
int dfn[MAXN],d[MAXN],id[MAXN],tl[MAXN],cnt;
int c[MAXN],t[MAXN];
void addt(int x,int y) {while(x <= n) t[x] += y,x += lowbit(x);return ;}
void addc(int x,int y) {while(x <= n) c[x] += y,x += lowbit(x);return ;}
int sumt(int x) {int as=0;while(x>0) as += t[x],x -= lowbit(x);return as;}
int sumc(int x) {int as=0;while(x>0) as += c[x],x -= lowbit(x);return as;}
void dfs(int x,int fa) {
    d[x] = d[fa] + 1;
    dfn[x] = ++ cnt;
    id[cnt] = x;
    tl[x] = cnt;
    for(int i = 0;i < g[x].size();i ++) {
        if(g[x][i] != fa) {
            dfs(g[x][i],x);
            tl[x] = max(tl[x],tl[g[x][i]]);
        }
    }
    return ;
}
int main() {
    n = read();m = read();
    root = 1;
    for(int i = 1;i < n;i ++) {
        s = read();o = read();
        ind[s] ++;ind[o] ++;
        g[s].push_back(o);
        g[o].push_back(s);
        if(ind[s] > 2) root = s;
        if(ind[o] > 2) root = o;
    }
    dfs(root,0);
    for(int i = 1;i <= m;i ++) {
        k = read();
        if(!k) {
            s = read();k = read();o = read();
            if(s == root) {
                addc(1,k);
                addc(2+o,-k);
//                cout<<"ok"<<endl;
            }
            else {
                bool flag = (d[s] <= o+1);
                int dis = o - d[s] + 1;
                int l,r;
                if(flag) l = dfn[s] - d[s] + 2 + dis;
                else l = dfn[s] - o;
                r = min(tl[s],dfn[s] + o);
                if(l <= r) addt(l,k),addt(r+1,-k);
                if(flag) addc(1,k),addc(2+dis,-k);
//                cout<<"OK"<<endl;
            }
        }
        else {
            s = read();
            printf("%d\n",sumt(dfn[s]) + sumc(d[s]));
        }
    }
    return 0;
}