题意：给一棵根为1号结点的树，每个点有权值，初始是0，(Q) 次操作,每次：
- 对深度为 (L) 的点全部加权值 (x)(根结点深度为0)
- 输出子树权值和
(n,Q leq 10^5)
先考虑操作2，显然这是个树上子树统计问题，dfs序+线段树/树状数组就可以在(O(log n))复杂度内完成。但是操作1，如果直接修改复杂度最坏则是(O(nlogn))(菊花图)，于是我们想到了一个最为经典的降低时间复杂度的方法——均摊。
思想就是因为操作2复杂度低，操作1复杂度高，那么就通过均摊一下把整体复杂度降低。
实现方法类似于分块。首先我们统计出每一层有哪些结点，然后根据结点个数分类。不妨规定一个(m)，当一层结点个数 (<m) 时进行暴力修改，复杂度(O(mlog n))，当结点个数(>m) 时打个标记。显然打标记的层数应该是不超过(frac{n}{m})个。然后统计答案时，对于每一个打标记的层，计算一下哪些结点在所求点的子树内。由于我们是按照dfs序统计的，那么每一层内dfs序是单调递增的，于是可以二分，对于统计的结点(x)，找到dfs序位于([dfn[x],dfn[x]+siz[x]])的结点，统计答案即可。
时间复杂度为(O(qmlog n + qfrac{n}{m}log n))，当 (m) 取 (sqrt{n})时复杂度最小，为(O(qsqrt{n} log n))
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<vector>
#include<set>
#include<map>
#include<string>
#include<iostream>
#include<queue>
#include<cctype>
#include<ctime>
using namespace std;
#define A(x) cout << #x << " " << x << endl;
#define AA(x,y) cout << #x << " " << x << " " << #y << " " << y << endl;
#define AAA(x,y,z) cout << #x << " " << x << " " << #y << " " << y << " " << #z << " " << z << endl;
#define B cout << "Break" << endl;
#define ll long long
#define inf 1000000000
int read()
{
char c = getchar();
int x = 0,f = 1;
while(!isdigit(c))
{
if(c == '-') f = -1;
c = getchar();
}
while(isdigit(c))
{
x = x * 10 + c - '0';
c = getchar();
}
return f * x;
}
#define N 100010
int head[N],nxt[N << 1],to[N << 1],dfn[N],til[N];//存树
ll tag[N],c[N];
vector<int>d[N];
vector<int>dep_geq_sqrt;
int n,q,ecnt,maxdep,tim;
void add_edge(int u,int v)
{
nxt[++ecnt] = head[u];
head[u] = ecnt;
to[ecnt] = v;
return;
}
ll lowbit(ll x) {return x & -x;}
void add(ll x,ll k)
{
while(x <= n)
{
c[x] += k;
x += lowbit(x);
}
return;
}
ll query(ll x)
{
ll ret = 0;
while(x > 0)
{
ret += c[x];
x -= lowbit(x);
}
return ret;
}
void dfs(int u,int fa,int dep)
{
maxdep = max(maxdep,dep);
dfn[u] = ++tim;
d[dep].push_back(dfn[u]);
for(int i = head[u];i;i = nxt[i])
{
int v = to[i];
if(v == fa) continue;
dfs(v,u,dep + 1);
}
til[u] = tim;
return;
}
int main()
{
n = read(),q = read();
for(int i = 1;i < n;++i)
{
int u = read(),v = read();
add_edge(u,v);add_edge(v,u);
}
dfs(1,0,0);
int m = sqrt(n);
for(int i = 0;i <= maxdep;++i)
if(d[i].size() > m) dep_geq_sqrt.push_back(i);
while(q--)
{
int op = read();
if(op == 1)
{
int l = read(),x = read();
if(d[l].size() > m)
tag[l] += x;
else
for(auto u : d[l]) add(u,x);
}
else
{
int x = read();
ll ans = query(til[x]) - query(dfn[x] - 1);
for(auto dep : dep_geq_sqrt)
{
auto l = lower_bound(d[dep].begin(),d[dep].end(),dfn[x]);
auto r = upper_bound(d[dep].begin(),d[dep].end(),til[x]);
ans += 1ll * tag[dep] * (r - l);
}
printf("%lld
",ans);
}
}
}