虽然这题是一道二合一，也不算难，但还是学到了很多东西啊，(k) 级儿子个数的五种求法！！我还是觉得四种比较好（
(k) 级儿子个数有五种求法，你知道么？ ——鲁迅
首先 (k) 级祖先很好求，离线的话dfs的时候开个栈就好了。长链剖分也可以但我不会，倍增什么的就不用说了。
树上启发式合并
就是求一个子树里为某一个深度的点的个数嘛，这个明显可以dsu on tree啊，开个桶记录下各种深度的有几个就好了。
复杂度：(O(nlogn))，应该不能过0_0
树状数组
转化为dfs序，就是一个区间里等于某一个数的个数，二维数点弱化版，离线+树状数组。
复杂度：(O(nlogn))
二分
给每个深度开一个vector，按照dfs序把点塞进去，询问时只要在对应深度的vector里二分出区间左右端点就好了。
这个做法虽然也是 (O(nlogn)) ，但它是在线的，很妙啊！！
长链剖分
这个是模板了吧，用一个简单的DP统计一下就好了
复杂度 (O(n))
因为我之前其实不会长链剖分所以就写了下代码……
#include<bits/stdc++.h>
#define ll long long
#define fr(i,x,y) for(int i=(x);i<=(y);i++)
#define rf(i,x,y) for(int i=(x);i>=(y);i--)
#define frl(i,x,y) for(int i=(x);i<(y);i++)
using namespace std;
const int N=1000003;
const int M=N<<1;
int n,q;
int cnt,head[N],Next[M],v[M];
vector<int> id[N];
int qk[N];
void read(int &x){
char ch=getchar();x=0;
for(;ch<'0'||ch>'9';ch=getchar());
for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';
}
void add(int x,int y){
Next[++cnt]=head[x];
head[x]=cnt;
v[cnt]=y;
}
int st[N],L;
int d[N],bc[N],ls[N],*f[N],*now=ls;
//vector<int> qry[N];
void predfs(int x,int fa,int dep){
st[dep]=x;
//int bc=0;
for(auto tmp:id[x])
if (dep>qk[tmp])
id[st[dep-qk[tmp]]].push_back(tmp);
id[x].resize(0);
for(int i=head[x];i;i=Next[i]){
predfs(v[i],x,dep+1);
if (d[v[i]]>d[bc[x]]) bc[x]=v[i];
}
d[x]=d[bc[x]]+1;
}
int ans[N];
void dfs(int x,int fa){
f[x][0]=1;
if (bc[x]) f[bc[x]]=f[x]+1,dfs(bc[x],x);
for(int i=head[x];i;i=Next[i]){
int tmp=v[i];
if (tmp==bc[x]) continue;
f[tmp]=now;now+=d[tmp];
dfs(tmp,x);
fr(j,1,d[tmp]) f[x][j]+=f[tmp][j-1];
}
for(auto tmp:id[x])
ans[tmp]=f[x][qk[tmp]]-1;
}
int main(){
read(n);read(q);
int x;
fr(i,2,n){
read(x);
add(x,i);
}
fr(i,1,q){
read(x);read(qk[i]);
id[x].push_back(i);
}
predfs(1,0,1);
f[1]=now;now+=d[1];
fr(i,1,n) for(auto j:id[i]) printf("%d ",j);puts("---");
dfs(1,0);
fr(i,1,q) printf("%d ",qk[i]==0?0:ans[i]);
return 0;
}
dfs+差分
这是标算，，想不到……
前面那个树状数组未免太大材小用了，因为我们只是求区间里等于一个数的个数，并不真的需要树状数组所维护的前缀和。
我们dfs的时候记录一个 (cnt_i) 表示dfs过的里面深度为 (i) 的有多少个，然后求一个子树里深度为 (d) 的个数只要把dfs这个子树前后的 (cnt_d) 减一减就好了。