终于认真写一次标题了
因为一些不明原因，之前对(dsu) (on) (tree)的理解没有完全写出来，在这里会一起写，因为两者极为相似。
先来看一下(dsu) (on) (tree)和长链剖分的对比。
(dsu) (on) (tree)实际上就是重链剖分，可以处理很多与子树有关且不带修改的题目（离线），复杂度：(mathcal{O}(nlogn))。
长链剖分实际上就是长链剖分，可以处理很多与深度有关且不带修改的题目（离线），复杂度：(mathcal{O}(n))。
可以看出，长链剖分比(dsu) (on) (tree)适用范围更小，但更优秀。（具体原因后面会口胡）
考虑一下两者的暴力，即为开一个数组维护信息，每次跑一边子树维护信息，再统计答案，复杂度显然(mathcal{O}(n^2))的。
实际上，我们的暴力相当于每次跑子树时清空一遍数组，再维护信息。（原暴力显然可以在线，后面会不动声色变为离线，方便我们优化）
因此，我们考虑保留，再将其他信息加入，可以优化。
如果信息和深度无关，考虑重链剖分，先跑轻儿子，并处理他的答案，注意这里我们要清除信息，再跑重儿子，保留信息，处理答案，再暴力扫一遍轻儿子维护信息即可。
而当信息和深度有关时，显然用长链剖分更优秀些，通过在一个信息数组上的覆盖，完成了上面的清除信息（此处指针实现。
例题：(Cnoi2019)雪松果树
板子，直接上代码，重点是这题卡空间，倍增过不了，(Vector)也有点悬……
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int f=1,w=0;char x=0;
while(x<'0'||x>'9') {if(x=='-') f=-1; x=getchar();}
while(x!=EOF&&x>='0'&&x<='9') {w=(w<<3)+(w<<1)+(x^48);x=getchar();}
return w*f;
}
const int N=1000010;
int num_edge,n,q,Top,ans[N];
int head[N],Dep[N],Max[N],Son[N];
int Stk[N],Tmp[N<<2],*f[N],*Now=Tmp;
vector<pair<int,int> > Que[N],Anc[N];
struct Edge{int next,to;} edge[N];
inline void Add(int from,int to)
{
edge[++num_edge].next=head[from];
edge[num_edge].to=to;
head[from]=num_edge;
}
inline void Dfs_For_Pre(int pos)
{
for(int i=head[pos];i;i=edge[i].next)
{
Dfs_For_Pre(edge[i].to);
if(Max[Son[pos]]<Max[edge[i].to]) Son[pos]=edge[i].to;
}
Max[pos]=Max[Son[pos]]+1;
}
inline void Dfs_For_Anc(int pos)
{
Stk[++Top]=pos;
for(int i=0;i<(int)Que[pos].size();i++)
if(Top>Que[pos][i].first)
Anc[Stk[Top-Que[pos][i].first]].push_back(Que[pos][i]);
for(int i=head[pos];i;i=edge[i].next) Dfs_For_Anc(edge[i].to);
Top--;
}
inline void Long_Chain_Div(int pos)
{
for(int i=head[pos];i;i=edge[i].next)
if(edge[i].to!=Son[pos])
f[edge[i].to]=Now,Now+=Max[edge[i].to],Long_Chain_Div(edge[i].to);
if(Son[pos]) f[Son[pos]]=f[pos]+1,Long_Chain_Div(Son[pos]);f[pos][0]=1;
for(int i=head[pos];i;i=edge[i].next)
if(edge[i].to!=Son[pos])
for(int j=1;j<=Max[edge[i].to];j++)
f[pos][j]+=f[edge[i].to][j-1];
for(int i=0;i<(int)Anc[pos].size();i++)
ans[Anc[pos][i].second]=f[pos][Anc[pos][i].first]-1;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("A.in","r",stdin);
#endif
n=read(),q=read();
for(int i=2,x;i<=n;i++) x=read(),Add(x,i);
for(int i=1,x,k;i<=q;i++)
x=read(),k=read(),Que[x].push_back(make_pair(k,i));
Dfs_For_Anc(1);Dfs_For_Pre(1);
f[1]=Now;Now+=Max[1]+1;Long_Chain_Div(1);
for(int i=1;i<=q;i++) printf("%d ",ans[i]);
}