题目传送门

1.题意

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

2.思路

直接对于每个点去暴力跑肯定是TLE的，所以要寻求改变。
可以把问题当成一棵树来看，问题转化成了求距离1号节点的距离超过k的点的位置，然后直接断开，那这样直接对于每个i连一条从fa[i]到i的边就好了，不过要注意可能在k-1这个父节点下面的点之间的距离也有超过k的，但是可以直接递归处理解决。

#include <bits/stdc++.h>

using namespace std;

// #define int long long
#define ll int
#define x first
#define y second
#define PII pair<int,int>
#define LL long long
#define pb push_back
#define pqp priority_queue<PII,vector<PII>,greater<PII> >
#define pqi priority_queue<int,vector<int>,greater<int> >
#define PSS pair<string,string>
#define in insert
#define line inline
#define sort(s) sort(s.begin(),s.end());
#define reverse(s) reverse(s.begin(),s.end());
// #define max_(s) *max_element(s.begin(), s.end())
#define V vector<int>
#define VV vector<V>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

int dx[]=  {0,-1,0,1,0,0},dy[]= {-1,0,1,0,0,0},dz[] = {0,0,0,0,-1,1};
const int N = 100010,M = N * 2,mod = 1e9+7;
int f[N];
int e[M],ne[M],h[N],w[M],idx;
int n,k;
int dist[N];
bool st[N];
int res;

void add(int a,int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int dfs(int u,int dep)
{
    int ret = dep;
    for(int i = h[u]; ~i; i = ne[i]){
        int j = e[i];
        ret = max(ret,dfs(j,dep + 1));
    }
    if(ret - dep + 1 == k && f[u] != 1) {
        res ++;
        return 0;
    }
    return ret;
}

void solve()
{
    memset(h,-1,sizeof h);
    cin >> n >> k;
    for(int i = 1; i <= n; i ++){
        cin >> f[i];
        if(i != 1) add(f[i],i);
    }
    if(f[1] != 1) f[1] = 1, res ++;
    dfs(1,0);
    cout << res << endl;
}

signed main()
{
    // IOS
    // init();
    // get_primes(N - 1);
    // int _; cin >> _;for(int i = 1; i <= _; i ++)
    solve();
}