题目链接：https://nanti.jisuanke.com/t/31451
Given a rooted tree ( the root is node $1$ ) of $N$ nodes. Initially, each node has zero point.
Then, you need to handle $Q$ operations. There're two types:
1 L X: Increase points by $X$ of all nodes whose depth equals $L$ ( the depth of the root is zero ). ($x \leq 10^8$)
2 X: Output sum of all points in the subtree whose root is $X$.
Input
Just one case.
The first lines contain two integer, $N,Q$. ($N \leq 10^5, Q \leq 10^5$).
The next $n-1$ lines: Each line has two integer $a,b$, means that node aa is the father of node $b$. It's guaranteed that the input data forms a rooted tree and node $1$ is the root of it.
The next $Q$ lines are queries.
Output
For each query $2$, you should output a number means answer.
题意：
给出一棵 $N$ 个节点的树，初始每个节点的权值均为 $0$，接下来给出 $Q$ 个操作，有两种操作：
第一种，修改操作，对所有深度为 $L$ 的节点（根节点的深度为 $0$），权值加上 $X$；
第二种，查询操作，查询以节点 $X$ 为根节点的子树（包含节点 $X$）内所有节点的权值和。
题解：
说实话，比赛的时候，想到了DFS序+线段树的操作，但是不会搞时间复杂度卡死。然而，要知道，神仙的时间复杂度和蒟蒻的时间复杂度是不一样的。
以下根据官方题解：
设定一个层内节点数的阈值 $T$，
当第 $L$ 层的节点数 $size_L < T$ 时，用DFS序把树拍平，
修改操作，可以直接暴力枚举所有节点进行 $O\left( {\log N} \right)$ 修改，时间复杂度为 $O\left( {T\log N} \right)$；
查询操作，直接就是 $O\left( {\log N} \right)$ 区间查询。
因此，两种操作合起来的时间复杂度 $O\left( {Q \cdot T\log N} \right)$。
当第 $L$ 层的节点数 $size_L \ge T$ 时，
修改操作，存储每一层节点的权值（因为同一层内节点的权值永远是一样的），直接 $O\left( 1 \right)$ 修改；
查询操作，直接暴力枚举层，对于每一层，使用二分查找，得到属于“根为$X$的子树”的节点的个数，时间复杂度 $O\left( {\frac{N}{T}\log N} \right)$。
因此，两种操作合起来的时间复杂度 $O\left( {Q \cdot \frac{N}{T}\log N} \right)$。
因此总的时间复杂度为 $O\left( {Q\log N\left( {T + \frac{N}{T}} \right)} \right)$，所以令 $T = \sqrt N$ 最优，时间复杂度为 $O\left( {Q\sqrt N \log N} \right)$。
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+; int n,q;
int T;
ll val_deep[maxn]; //存储深度为deep的节点的权值
vector<int> Node_deep[maxn]; //存储深度为deep的节点的编号
vector<int> bigL; //存储节点数不小于阈值的层编号 //邻接表-st
struct Edge{
int u,v;
Edge(int u=,int v=){this->u=u,this->v=v;}
};
vector<Edge> E;
vector<int> G[maxn];
void addedge(int u,int v)
{
E.push_back(Edge(u,v));
G[u].push_back(E.size()-);
}
//邻接表-ed //dfs序-st
int dfs_clock=;
int in[maxn],out[maxn];
void dfs(int now,int dep)
{
in[now]=++dfs_clock;
Node_deep[dep].push_back(in[now]);
for(int i=;i<G[now].size();i++)
{
int nxt=E[G[now][i]].v;
dfs(nxt,dep+);
}
out[now]=dfs_clock;
}
//dfs序-ed struct _BIT{
int N;
ll C[maxn];
int lowbit(int x){return x&(-x);}
void init(int n) //初始化共有n个点
{
N=n;
for(int i=;i<=N;i++) C[i]=;
}
void add(int pos,ll val) //在pos点加上val
{
while(pos<=N)
{
C[pos]+=val;
pos+=lowbit(pos);
}
}
ll sum(int pos) //查询1~pos点的和
{
ll ret=;
while(pos>)
{
ret+=C[pos];
pos-=lowbit(pos);
}
return ret;
}
}BIT; int main()
{
cin>>n>>q;
T=((n>)?(int)sqrt(n):n);
for(int i=;i<n;i++)
{
int par,son; scanf("%d%d",&par,&son);
addedge(par,son);
} dfs(,); for(int dep=;dep<=n;dep++)
{
if(Node_deep[dep].size()>=T) bigL.push_back(dep);
} BIT.init(n);
memset(val_deep,,sizeof(val_deep));
for(int i=;i<=q;i++)
{
int type; scanf("%d",&type);
if(type==)
{
int L,X; scanf("%d%d",&L,&X);
if(Node_deep[L].size()<T)
for(int k=;k<Node_deep[L].size();k++) BIT.add(Node_deep[L][k],(ll)X);
else
val_deep[L]+=X;
}
else
{
int X; scanf("%d",&X);
ll ans=BIT.sum(out[X])-BIT.sum(in[X]-);
for(int k=;k<bigL.size();k++)
{
int dep=bigL[k];
int L=lower_bound(Node_deep[dep].begin(),Node_deep[dep].end(),in[X])-Node_deep[dep].begin();
int R=upper_bound(Node_deep[dep].begin(),Node_deep[dep].end(),out[X])-Node_deep[dep].begin();
ans+=(R-L)*val_deep[dep];
}
printf("%lld\n",ans);
}
}
}
评测结果：
可以看到，名字叫卡常的题目是最不卡常的。