题目链接：https://nanti.jisuanke.com/t/31451
题意：
给你一颗树，树上各点有初始权值，你有两种操作：
1. 给树中深度为l的点全部+x,(根节点为1，深度为0）
2.求出以x为根的子树权值和
思路：
因为第一个操作是对一整层的树节点+x，那么我们可以很容易的标记每一层一共加了多少权值，那么子树增加的就是以x为根到叶子节点每一层增加的值之和乘以这颗子树当前层的节点数，我们可以用二分快速找到每一层的节点个数，但是我们还是会发现，这样每一次操作极限时间复杂度还是很高，我们要尽量将它在优化下，我们可以发现如果当前层节点数较少的情况下，上面的方法并不是很优越，那么对节点数少小的层我们可以直接用bit更新，复杂度会优越很多，判断的界限直接设为sqrt(n)，类似分块的思维，小一点的bit更新，大的标记数组，这样我们每一次询问某个树的子树权值和就把标记数组和bit中的值加起来就好了。
实现代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int M = 2e5+; int in[M],out[M],n,cnt,tot,head[M],dep;
ll ans[M],c[M<<];
vector<int>d[M];
vector<int>q;
struct node{
int to,next;
}e[M]; void add(int u,int v){
e[++cnt].to = v;e[cnt].next = head[u];head[u] = cnt;
} void dfs(int u,int fa,int deep){
dep = max(dep,deep); //最大层数
in[u] = ++tot;
d[deep].push_back(in[u]); //每一层分别有哪些节点
for(int i = head[u];i;i=e[i].next){
int v = e[i].to;
if(v == fa) continue;
dfs(v,u,deep+);
}
out[u] = tot;
} void add(int x,ll v){
while(x <= n){
c[x] += v;
x += (x&-x);
}
} ll getsum(int x){
ll ret = ;
while(x){
ret += c[x];
x -= (x&-x);
}
return ret;
} int main()
{
int m,x,u,v,block;
ll y;
tot = ;cnt = ;
scanf("%d%d",&n,&m);
for(int i = ;i < n;i ++){
scanf("%d%d",&u,&v);
add(u,v); add(v,u);
}
dep = ;
dfs(,,);
block = sqrt(n);
for(int i = ;i <= dep;i ++){
if(d[i].size()>block) q.push_back(i); //把大的块的编号存起来
}
int op;
while(m--){
scanf("%d",&op);
if(op == ){
scanf("%d%lld",&x,&y);
if(d[x].size() > block) ans[x] += y; //大的块标记数组
else{
for(int i = ;i < d[x].size();i++) //小的块bit更新
add(d[x][i],y);
}
}
else {
scanf("%d",&x);
ll num = getsum(out[x]) - getsum(in[x]-); //小的块的值
for(int i = ;i < q.size();i ++){
num += 1LL*(upper_bound(d[q[i]].begin(),d[q[i]].end(),out[x])-lower_bound(d[q[i]].begin(),d[q[i]].end(),in[x]))*ans[q[i]]; //每次层的数量*这一层标记数组的值
}
printf("%lld\n",num);
}
}
return ;
}