問題
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; }