题目链接：https://cn.vjudge.net/problem/Gym-100589A
#include<bits/stdc++.h>
using namespace std;#define debug puts("YES");
#define rep(x,y,z) for(int (x)=(y);(x)<(z);(x)++)
#define read(x,y) scanf("%d%d",&x,&y)
#define ll long long#define lrt int l,int r,int rt
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
/*
题目大意:一棵树两种操作，
查询子树的权重和，修改同一层节点的权重。同一层的节点的话就用vector来分层，记住要记录
DFS区间序的左端点即可。首先思考下，同一层的修改操作，
有两种，一种是在层权重数组中直接修改，O(1),
然后查询时遍历所有层，通过二分来统计节点累加权重。O(nlogn)
一种是树状数组通过DFS序左端点修改，O(nlogn)
查询时可以直接树状数组查询区间和O(logn)。
如果我们采用其中的任何一种，为什么会超时呢？
因为存在某一层节点数量太多的情况，直接使复杂度弱化为O(nmlogn)。
这样就要引入数据结构中常用的分块的思想（不是数论中的分块。。。）
个人感觉其实就是均摊，当深度节点数量大于X时，采用第二种修改，
否则采用第一种，至于查询，N/x*logn级别的。因为这样需要统计权重的层数
不超过N/x。
那么我们把函数式子列出来发现x取根号N答案最优，根号N的界限就是这样来的。有了思路下面就是秀操作的时候了。
另外一个小优化是要事先把大于界限的层下标抽取出来。
*/
const int maxn =1e5+5;
///数据范围区域
int n,m,ub;
int op,x,y;
///深度节点集合和权重数组
vector<int> g[maxn],big;
ll w[maxn];///数据范围要注意
int maxd;
///链式前向星
struct node
{int u,nxt;
}edge[maxn<<1];
int head[maxn],tot=0,ti;
void init()
{big.clear();for(int i=0;i<=n;i++) g[i].clear();memset(w,0,sizeof(w));memset(head,-1,sizeof(head));tot=ti=maxd=0;
}
void add(int x,int y)
{edge[tot]=node{y,head[x]};head[x]=tot++;
}
///DFS序区间建立
int pl[maxn],pr[maxn];
void dfs(int u,int pre,int h)
{maxd=max(maxd,h);pl[u]=++ti;g[h].push_back(ti);for(int i=head[u];~i;i=edge[i].nxt){int v=edge[i].u;if(v==pre) continue;dfs(v,u,h+1);}pr[u]=ti;
}
///bit
ll tree[maxn<<1];
int lowbit(int x)
{return x&(-x);
}
void refresh(int x,int d)
{for(;x<maxn;tree[x]+=d,x+=lowbit(x));
}
ll sum(int x)
{ll ret=0;for(;x>0;ret+=1LL*tree[x],x-=lowbit(x));return ret;
}
int main()
{init();scanf("%d%d",&n,&m);ub=sqrt(n);for(int i=1;i<n;i++){scanf("%d%d",&x,&y);add(x,y),add(y,x);}dfs(1,-1,0);///建立DFS序for(int i=0;i<=maxd;i++){if(g[i].size()<=ub) continue;sort(g[i].begin(),g[i].end());big.push_back(i);}for(int i=0;i<m;i++){scanf("%d",&op);if(op==1){scanf("%d%d",&x,&y);int sz=g[x].size();if(sz<=ub)///树状数组暴力修改{for(int j=0;j<sz;j++)refresh(g[x][j],y);}else{w[x]+=y;}}else{scanf("%d",&x);int l=pl[x],r=pr[x],sz=big.size();ll ans=1LL*(sum(r)-sum(l-1));///log查询for(int j=0;j<sz;j++){int d=big[j];int tx=upper_bound(g[d].begin(),g[d].end(),pr[x])-g[d].begin();int ty=lower_bound(g[d].begin(),g[d].end(),pl[x])-g[d].begin();ans+=1LL*(tx-ty)*w[d];}printf("%lld\n",ans);}}return 0;
}