Teleporter

Description
有 n個城市,每個城市有一個傳送點,都可以傳送到唯一的另外一個城市,保證從任何位置出發經過若干次傳送之后能夠到達 1號城市?，F在希望修改一些點的目的地,使得從任何一點出發在傳送 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);}