思路：

dfs序+树状数组+分块

先dfs处理好每个节点的时间戳

对于每一层，如果这一层的节点数小于sqrt(n)，那么直接按照时间戳在树状数组上更新

如果这一层节点个数大于sqrt(n)，那么直接存一下这一层每个节点的大小（都是一样的），这样的层数不会超过sqrt(n)层

然后查询的时候先在树状数组查询答案，然后再遍历第二种层数，加到答案中

复杂度：n*sqrt(n)*log(n)

代码：

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
     
      using namespace std;#define fi first#define se second#define pi acos(-1.0)#define LL long long#define mp make_pair#define pb push_back#define ls rt<<1, l, m#define rs rt<<1|1, m+1, r#define ULL unsigned LL#define pll pair
      
       #define pii pair
       
        #define piii pair
        
         #define mem(a, b) memset(a, b, sizeof(a))#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);//headconst int N = 1e5 + 10;vector
         
          g[N];int in[N], out[N], deep[N], n, tot = 0;LL val[N], bit[N];vector
          
           dfn[N];vector
           
            big;void add(int x, int v) { while(x <= n) bit[x] += v, x += x&-x;}LL query(int x) { LL ans = 0; while(x) ans += bit[x], x -= x&-x; return ans;}void dfs(int o, int u, int d) { deep[u] = d; in[u] = ++tot; dfn[d].pb(tot); for (int v:g[u]) { if(v != o) dfs(u, v, d+1); } out[u] = tot;}int main() { int q, u, v, blo, ty, l, x; scanf("%d %d", &n, &q); blo = sqrt(n); for (int i = 1; i < n; i++) { scanf("%d %d", &u, &v); g[u].pb(v); g[v].pb(u); } dfs(1, 1, 0); for(int i = 0; i < n; i++) { if(dfn[i].size() > blo) big.pb(i); } while(q--) { scanf("%d", &ty); if(ty == 1) { scanf("%d %d", &l, &x); if(dfn[l].size() <= blo) { for (int i = 0; i < dfn[l].size(); i++) { add(dfn[l][i], x); } } else val[l] += x; } else { scanf("%d", &x); LL ans = query(out[x]) - query(in[x]-1); for (int i = 0; i < big.size(); i++) { int d = big[i]; int t = upper_bound(dfn[d].begin(), dfn[d].end(), out[x]) - lower_bound(dfn[d].begin(), dfn[d].end(), in[x]); ans += 1LL * t * val[d]; } printf("%lld\n", ans); } } return 0;}