AGC004_D Teleporter

题面翻译：
有n个城市，每个城市有一个传送点，都可以传送到唯一的另外一个城市，保证从任何位置出发经过若干次传送之后能够到达1号城市。现在希望修改一些点的目的地，使得从任何一点出发在传送K次之后恰好都能到达1号城市，求最少要改变目的地的城市的数量。
Translated by @加藤圣教_封仙

思路：
首先一号点必须连向自己，因为存在两个点，一个点到1号点的最短路径等于另一个点的路径+1，而你每次只能经过环来增加自己的路径长度，然而只存在一个环，所以此环长度必为1。之后我们就只要让所有点到1号点的最短路径小于等于k即可。我们可以贪心的想，每次将深度最深的点往上走k-1步的点连向1号点即可，然后那个点的子树就均满足条件了。空间O(n),时间O(n)。

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=1e5;
int n,k,ans,tot;
vector<int>vr[maxn+8];
int pre[maxn+8],now[maxn+8],son[maxn+8],dep[maxn+8],fa[maxn+8];
bool vis[maxn+8];

int read()
{
    int x=0,f=1;char ch=getchar();
    for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
    for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
    return x*f;
}

void add(int u,int v)
{
    pre[++tot]=now[u];
    now[u]=tot;
    son[tot]=v;
}

void dfs(int x)
{
    vr[dep[x]].push_back(x);
    for (int p=now[x];p;p=pre[p])
	{
	    int child=son[p];
	    fa[child]=x;dep[child]=dep[x]+1;
	    dfs(child);
	}
}

void solve(int x)
{
    for (int i=1;i<=k;i++)
	{
	    if (vis[x]) return;
	    vis[x]=1;
	    x=fa[x];
	}
    ans+=(x!=1);
}

int main()
{
    n=read(),k=read();
    int x=read();if (x!=1) ans=1;
    for (int i=2;i<=n;i++)
	{
	    int f=read();
	    add(f,i);
	}
    dfs(1);
    vis[1]=1;
    for (int i=n;i;i--)
	for (vector<int>::iterator it=vr[i].begin();it!=vr[i].end();it++)
	    solve(*it);
    printf("%d
",ans);
    return 0;
}