はまやんはまやんはまやん

hamayanhamayan's blog

Teleporter [AGC 004 : D]

問題

http://agc004.contest.atcoder.jp/tasks/agc004_d

町1~Nがある。
町1は首都。
どの町にもテレポータが1つあり、町iから町a[i]へテレポートできる。
どの町から出発してもテレポートをちょうどK回すると首都につけるようにテレポートの行き先を変える。
最小で何個のテレポート先を変えればよいか。

2 <= N <= 10^5
1 <= K <= 10^9

帰納的考察(Editorial見た)

1. 「ちょうどK回というのが気になる」
2. これについて考えると、町1は自分を指す必要があると分かる
3. すると、辺の数がN-1個となり、木となる
4. 木といえばDFSだし、Nの制約もちょうどよい

5. 町1を自分とすると、K回以内のテレポートでつければいい
6. 木で考えると深さがK以下になるように辺を変えればよさそう
7. ここまで分かったんやけど…

――壁――

8. 根からの深さじゃなく、葉からの深さを考える
9. なるほどなー
10. 葉から数えて深さがKとなったら町1へ辺を貼り直す

実装

http://agc004.contest.atcoder.jp/submissions/870349

int N, K;
int ai;
vector<int> E[101010];
//-----------------------------------------------------------------
int ans = 0;
int dfs(int cur, int par) {
	int m = 0;
	for (int to : E[cur]) if (to != par) {
		m = max(m, dfs(to, cur));
	}
	m++;
 
	if (cur == 1 || par == 1) return 0;
	if (m < K) return m;
 
	ans++;
	return 0;
}
//-----------------------------------------------------------------
int main() {
	cin >> N >> K >> ai;
	rep(i, 1, N) {
		int a; cin >> a;
		E[a].push_back(i + 1);
		E[i + 1].push_back(a);
	}
 
	dfs(1, 0);
 
	if (ai != 1) ans++;
	cout << ans << endl;
}