我的作业：agc004d

一.题目大意

Snuke王国有$$n$$座城镇，标号为$$1$$到$$n$$，城镇$$1$$为首都。
王国中每一座城镇有一个传送器：一个立即将人传送到另一个地方的设施。城镇$$i$$的传送目的地为$$a_i(1\le a_i \le N)$$，保证一个人可以在任意城镇使用几次传送器到达首都。
国王Snuke喜爱数字$$K$$，这个自私的国王想要修改传送器的目的地使其满足如下条件：
$$\bullet$$ 一个人可以从任意城镇开始经过恰好$$K$$次传送后到达首都。

求要满足条件需要修改目的地的传送器个数的最小值。

$$2\le N\le 10^5$$
$$1\le a_i\le N$$
$$1\le K\le 10^9$$

二.解题报告

将城市看成点，每个城市向该城市的传送目的地连边，初始时由于每个点出度都为$$1$$且都可以到达$$1$$点，因此这个图为一棵基环内向树，且$$1$$点在环上。

修改后的图同样为基环内向树，为了满足从任意城镇经过恰好$$K$$次传送后到达首都，环必须为$$1$$点的自环，且树的深度小于等于$$K+1$$。

首先将$$1$$点的传送目的地改为自身。不考虑这个自环，将图看成一棵以$$1$$点为根的树，现在需要将一些点的父亲修改，使树的深度小于等于$$K+1$$。

显然将父亲修改为其他点不会比修改为$$1$$点更优，因此可以采用如下的贪心策略：从叶节点向上进行树形dp，到一个点时如果该点子树中深度最大的叶子到该点距离为$$K-1$$，那么将该点的父亲修改为$$1$$点。

易证这个贪心策略的正确性，因为修改深度小的点的父亲显然比修改深度大的点的父亲更优。

时间复杂度$$O(n)$$

#include <bits/stdc++.h>
using namespace std;
#define N 110000
int n,K,ans;
int a[N];
vector<int>vec[N];
int dfs(int x)
{
    int ret=0;
    for(int i=0;i<vec[x].size();i++)
    {
        int t=dfs(vec[x][i]);
        if(t==K)ans++;
        else ret=max(ret,t);
    }
    return ret+1;
}
int main()
{
    //freopen("tt.in","r",stdin);
    scanf("%d%d",&n,&K);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        if(i!=1)vec[a[i]].push_back(i);
    }
    ans=(a[1]!=1);
    for(int i=0;i<vec[1].size();i++)
        dfs(vec[1][i]);
    printf("%d\n",ans);
    return 0;
}