「AGC004D」Teleporter (800pts) - 贪心

题目链接 : D: Teleporter

简要题意

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

Teleporter

Time limit : 1sec / Memory limit : 256MB

Score : 800 points

Problem Statement

There are N towns in Snuke Kingdom, conveniently numbered 1 through N. Town 1 is the capital.

Each town in the kingdom has a Teleporter, a facility that instantly transports a person to another place. The destination of the Teleporter of town i is town ai ( 1≤a_i≤N ). It is guaranteed that one can get to the capital from any town by using the Teleporters some number of times.

King Snuke loves the integer K. The selfish king wants to change the destination of the Teleporters so that the following holds:

Starting from any town, one will be at the capital after using the Teleporters exactly K times in total.

Find the minimum number of the Teleporters whose destinations need to be changed in order to satisfy the king's desire.

Constraints

2≤N≤10^5 1≤a_i≤N

One can get to the capital from any town by using the Teleporters some number of times. 1≤K≤109

Input

The input is given from Standard Input in the following format:

N K

a1 a2 … aN

Output

Print the minimum number of the Teleporters whose destinations need to be changed in order to satisfy King Snuke's desire.

Samples

题解

zz了....每次看到这种贪心题都看不出来

由于第一个点走 k 步能到达 1 ,所以最优的办法是 1 弄一个自环,绕 k 圈就完事了(

剩下就是 n 个点 n - 1 条边的问题了。这就是一颗以 1 为根的树(,如果到达 1 的步数小于 k ,可以在 1 的自环上多绕几圈,如果到 1 的步数大于 k 就直接贪心接到其他树上就好了

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const int N = 100000 + 10;

int n, k, ans;
std::vector <int> e[N];
int v[N];

int dfs (int u, int dep = 0) {
int ret = dep;
for (auto i : e[u]) ret = std::max(ret, dfs(i, dep + 1));
if (v[u] ^ 1 && ret - dep == k - 1) {
ans++;
return 0;
}
return ret;
}

int main () {
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++) scanf("%d", v + i);
if (v[1] ^ 1) v[1] = 1, ans++;
for (int i = 2; i <= n; i++) e[v[i]].push_back(i);
dfs(1); printf("%d", ans);
return 0;
}
坚持原创技术分享,您的支持将鼓励我继续创作!