[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;
}