题意:给一棵根为1号结点的树,每个点有权值,初始是0,\(Q\) 次操作,每次:
- 对深度为 \(L\) 的点全部加权值 \(x\)(根结点深度为0)
- 输出子树权值和
\(n,Q \leq 10^5\)
先考虑操作2,显然这是个树上子树统计问题,dfs序+线段树/树状数组就可以在\(O(\log n)\)复杂度内完成。但是操作1,如果直接修改复杂度最坏则是\(O(nlogn)\)(菊花图),于是我们想到了一个最为经典的降低时间复杂度的方法——均摊。
思想就是因为操作2复杂度低,操作1复杂度高,那么就通过均摊一下把整体复杂度降低。
实现方法类似于分块。首先我们统计出每一层有哪些结点,然后根据结点个数分类。不妨规定一个\(m\),当一层结点个数 \(<m\) 时进行暴力修改,复杂度\(O(m\log n)\),当结点个数\(>m\) 时打个标记。显然打标记的层数应该是不超过\(\frac{n}{m}\)个。然后统计答案时,对于每一个打标记的层,计算一下哪些结点在所求点的子树内。由于我们是按照dfs序统计的,那么每一层内dfs序是单调递增的,于是可以二分,对于统计的结点\(x\),找到dfs序位于\([dfn[x],dfn[x]+siz[x]]\)的结点,统计答案即可。
时间复杂度为\(O(qm\log n + q\frac{n}{m}\log n)\),当 \(m\) 取 \(\sqrt{n}\)时复杂度最小,为\(O(q\sqrt{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\n",ans);
}
}
}