2018.8.11T1（贪心，基环树）

贪心，基环树）"/>

2018.8.11T1（贪心，基环树）

描述
有 n 座城市，其中编号为 1 的是首都。

城市之间只能通过单向的传送器进行移动。每座城市有且仅有一个传送器，第 i 个城市的传送器指向城市 ai。保证从任意城市出发，经过若干次传送，都能到达首都。

小A喜欢 K 这个数，他想让你修改一些城市的传送器，使得从每个城市出发，走恰好 K 步后都能恰好停在首都。

求最少需要修改多少个城市的传送器。

输入格式
第一行两个数 n, K。

第二行 n 个数 a1~an，表示每个城市初始的传送器指向的城市编号。

输出格式
一行一个数，表示最少需要修改多少个城市的传送器。

样例1
样例输入1
3 1
2 3 1
样例输出1
2
样例2
样例输入2
8 2
5 4 2 1 1 7 2 4
样例输出2
3

仔细观察你会发现，题目绕来绕去，就是给了你一个树形结构
不过这是一个奇环内向树
实际上是单个环
当然如果你足够优秀，你会直接发现1必须连自己，然后你随便给每个节点重新定父亲，问最少需要给几个节点重新定父亲
实际上我们只要贪心的做就行了
很多人的做法是从上往下搜，把 k+1,2k+1,3k+1 k + 1 , 2 k + 1 , 3 k + 1 $k+1,2k+1,3k+1$层全部改掉
实际上这样是错的，不是最优的
要从下往上搜
为什么？
实际上抽象的想，从上往下相当于把从上往下选择的层向上移若干层。
那移动之后的点数肯定比移动前的点数要少。
故从下往上搜肯定比从上往下搜更优

#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i = j;i <= k;++i)
#define repp(i,j,k) for(int i = j;i >= k;--i)
#define ll long long
int n , k;
int a[100100] , fa[100100] , hash[100100];
struct deep{int num , id;
}dep[100100];
vector<int>G[100100];
bool flag[100100];
int read()
{int sum = 0;char c = getchar();bool flag = true;while( c < '0' || c > '9' ) {if(c == '-') flag = false;c = getchar();}while( c >= '0' && c <= '9' ) sum = sum * 10 + c - 48 , c = getchar();if(flag)  return sum;else return -sum;
}  
queue<int>q;
void print1()
{int now = 0;rep(i,1,n) if(a[i] != 1) now++;printf("%d\n",now);exit(0);
}
void change(int x)
{fa[x] = 1;q.push(x);dep[hash[x]].num = 1;while(q.size()){int x = q.front();flag[x] = true;rep(i,1,G[x].size()){if(flag[G[x][i-1]]) continue;dep[hash[G[x][i-1]]].num = dep[hash[x]].num + 1;q.push(G[x][i-1]);}q.pop();}return;
}
bool mycmp(deep a,deep b)
{return a.num > b.num;
}
int solve1()
{int sum = 0;sort(dep + 1,dep + n + 1,mycmp);rep(i,1,n) hash[dep[i].id] = i; rep(i,1,n)if(dep[i].num <= k) continue;else{int now = dep[i].id;rep(i,1,k-1) now = fa[now];change(now);sum++;}if(a[1] != 1) sum++;return sum;
}
void init()
{n = read();k = read();rep(i,1,n) {a[i] = read();if(i == 1) continue;G[a[i]].push_back(i);fa[i] = a[i];}if(k == 1) print1();q.push(1);while(q.size()){int x = q.front();rep(i,1,(G[x].size())){dep[G[x][i-1]].num = dep[x].num +1;q.push(G[x][i-1]);}q.pop();}rep(i,1,n) dep[i].id = i;printf("%d\n",solve1());return;
}
int main()
{init();return 0;
}