题解：
和正解方法不太一样
正解的大概意思就是先向下走可以走回来的 再走不能走回来的
能走回来的就是到这个儿子后最近的叶子可以返回的
然后这样可以O(n)计算
我自己做的时候以为这样不太能做。。
所以用的是哪些点可以返回当前点
途中可以利用其它叶子
可以发现如果可以利用其他叶子到达，那多个的时候也可以到达
于是我们只需要统计一条链上能到达的最大值
这个可以线段树维护一下
代码：
#include <bits/stdc++.h>
using namespace std;
#define rint register int
#define IL inline
#define rep(i,h,t) for (int i=h;i<=t;i++)
#define dep(i,t,h) for (int i=t;i>=h;i--)
#define mid ((h+t)>>1)
const int N=1.1e6;
const int INF=1e9;
int head[N],l,n,k;
int bz[][N],dfn[N],num[N],dy[N],cnt,p[N],ans[N];
bool t[N];
struct re{
int a,b;
}e[N*];
IL void arr(int x,int y)
{
e[++l].a=head[x];
e[l].b=y;
head[x]=l;
}
void dfs(int x,int y)
{
bz[][x]=y; dfn[x]=++cnt; num[x]=; dy[cnt]=x;
for (rint u=head[x];u;u=e[u].a)
{
int v=e[u].b;
if (v!=y)
{
dfs(v,x);
num[x]+=num[v];
}
}
}
IL int js(int x)
{
int k1=k;
dep(i,,)
if (k1>(<<i))
{
x=bz[i][x]; k1-=(<<i);
}
x=bz[][x];
if (x) return x; else return ;
}
struct sgt{
int v[N*];
sgt() { rep(i,,N*-) v[i]=INF;}
void change(int x,int h,int t,int pos,int k)
{
v[x]=min(v[x],k);
if (h==t) return;
if (pos<=mid) change(x*,h,mid,pos,k);
else change(x*+,mid+,t,pos,k);
}
int query(int x,int h,int t,int h1,int t1)
{
if (h1<=h&&t<=t1)
{
return v[x];
}
int ans=INF;
if (h1<=mid) ans=query(x*,h,mid,h1,t1);
if (mid<t1) ans=min(ans,query(x*+,mid+,t,h1,t1));
return ans;
}
}S;
queue<int> q;
void bfs()
{
q.push(); S.change(,,n,,);
while (!q.empty())
{
int x=q.front(); q.pop();
if (!t[x])
{
int tmp=S.query(,,n,dfn[p[x]],dfn[p[x]]+num[p[x]]-);
tmp=min(tmp,dfn[p[x]]);
ans[dy[tmp]]++;
S.change(,,n,dfn[x],tmp);
}
for (rint u=head[x];u;u=e[u].a)
{
int v=e[u].b;
if (v!=bz[][x]) q.push(v);
}
}
}
void dfs2(int x,int y)
{
ans[x]+=ans[y];
for (rint u=head[x];u;u=e[u].a)
{
int v=e[u].b;
if (v!=y) dfs2(v,x);
}
}
int main()
{
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
ios::sync_with_stdio(false);
cin>>n>>k;
rep(i,,n)
{
int x;
cin>>x; t[x]=;
arr(x,i);
}
dfs(,);
rep(i,,)
rep(j,,n)
bz[i][j]=bz[i-][bz[i-][j]];
rep(i,,n) p[i]=js(i);
bfs();
dfs2(,);
int ansa=;
rep(i,,n) if (ans[i]>ansa) ansa=ans[i];
cout<<ansa<<endl;
return ;
}