[AGC004D] Teleporter 题解

题目链接：[AGC004D] Teleporter

题意：

cxy 王国中有 $N$ 个城镇，方便地从 $1$ 到 $N$ 编号。城镇 $1$ 是首都。

该王国中的每个城镇都有一个传送门，该设施可立即将人传送到另一个地方。城镇 $i$ 的传送门的目的地是城镇 $a_i$（$1\leq a_i\leq N$）。保证可以通过使用传送门从任何城镇到达首都。

国王 cxy 喜欢整数 $K$。自私的国王希望更改传送门的目的地，以满足以下条件：

从任何城镇开始，使用传送门正好 $K$ 次后，将到达首都。

找到需要更改目的地的传送门的最小数量，以满足国王的愿望。

输入格式：

输入以以下格式从标准输入中给出：

$N$ $K$

$a_1$ $a_2$ … $a_N$

数据范围：

$2\leq N\leq 10^5,~1\leq a_i\leq N,~1\leq K\leq 10^9$

数据保证可以通过使用传送门从任何城镇到达首都。

输出格式：

输出需要更改目的地的传送门的最小数量，以满足 cxy 国王的愿望。

首先容易发现，当 $1$ 指向的不是自己时，会出现一个环，进而原图变成基环树。

这个环的存在没有任何好处，首先可能导致奇偶性问题，其次可能会增加调整奇偶性的花费。

因此最好的办法就是把 $1$ 变成一个自环，这样只需要考虑路线超过 $k$ 的情况怎么办了。

不难发现，如果 $u$ 到 $1$ 的距离为 $k + 1$ ，则我们直接把 $u$ 所在子树挂到 $1$ 上，

即 $u$ 指向 $1$ 一定是最优的选择，其正确性显然。因此我们只需遍历一遍原树即可。

时间复杂度 $\mathcal{O}(n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))

vector<int> vec[N];
int n,k,res,a[N];
int dfs(int u,int f,int dep)
{
    int mx = dep;
    for(int v : vec[u]) 
    {
        if(v == f) continue;
        up(mx, dfs(v,u,dep+1));
    }
    if(a[u] != 1 && mx - dep == k - 1) { return ++res, 0; }
    return mx;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> a[i];
    if(a[1] != 1) res = a[1] = 1;
    for(int i = 2; i <= n; i++) {
        vec[i].push_back(a[i]), vec[a[i]].push_back(i);
    }
    dfs(1,0,0); cout << res << '\n';
    return 0;
}