Description
有 n个城市,每个城市有一个传送点,都可以传送到唯一的另外一个城市,保证从任何位置出发经过若干次传送之后能够到达 1号城市。现在希望修改一些点的目的地,使得从任何一点出发在传送 K次之后恰好都能到达 1号城市,求最少要改变目的地的城市的数量。

Format
Input
第一行给出数字N

第二行给出N个数字,代表每个城市其传送点可到的城市

N<=1e5

Output
如题

Samples
输入数据 1
3 1
2 3 1
输出数据 1
2
输入数据 2
3 1
2 3 1 2
输出数据 2
3

Sol
按题目意思,原图中必然是存在环的。
只有这样所有点才能必然走到1.

此时如果我们希望从1出发走到其它点的话
则需将原图的边,反向建边
这样在反图上,1可以走到其它点,则在原图上
其它点也可以走到1上。

于是在反图上我们进行如下操作
1:如果1自己指向的不是1本身的话
则需要建立一个这样的边出来,也就是说形成自环。
这样可以非常方便的进行后面的操作。
例如

这样的图,K=4
1确实是可以经过4步后回到自己,再其它点就难操作了。
但建好自环后,其它点不要做任何变化,都可以经过4步走到1.
例如可以在1上先转3圈,再走到2;在1上先转2圈,再走到3;在1上先转1圈,再走到4;

接下来关于如何修改点的操作
对于下图,设K=2,

我们发现从1出发,2步之内是可以走到2和3的
但走不到4和5.
于是我们可以加条边1-->3,这样就可以了。
也就是说3的深度为2,其最大子树深度为3.两者之差正好为K-1.
于是加条边1-->3,便可达到目标了。
注意是正好等于k-1时,也是说1所指向的点,应该深度应该尽可能小一点
这样可以覆盖到尽可以多的点.

#include<iostream>#include<cstdio>using namespace std;int n,k,ans=0;int tot=0,h[100005],a[100005];struct Edge{int x,next;}e[200005];inline void add_edge(int x,int y){e[++tot].x=y;e[tot].next=h[x];h[x]=tot;}int dfs(int x,int deep){ int ret=deep;for(int i=h[x];i;i=e[i].next)ret=max(ret,dfs(e[i].x,deep+1));if(a[x]!=1&&ret-deep==k-1)//如果x这个点的深度与其最深的叶子点深度差为k-1时    //并且x的转移点并不为1时,就要加边了 {    return ans++,0;    }else      return ret;}int main(){scanf("%d%d",&n,&k);for(int i=1;i<=n;i++)   scanf("%d",a+i);//2 3 1 if(a[1]!=1)    ans=a[1]=1;for(int i=2;i<=n;i++)     add_edge(a[i],i);//反向建图,这样保证可以从1号点走到其它所有点 dfs(1,0),printf("%d",ans);}