Educational Codeforces Round 7 E. Ants in Leaves
かみぺコン 2 の Waiwai Otaku Panic を連想してた。
解法
根が持つ部分木のひとつに着目する。この部分木の根からそれぞれの葉までの距離をリストに入れる。
根から葉までの距離を到着予定時刻と考える。
| 到着予定時刻 | 1 | 2 | 2 | 2 | 3 | 3 | 8 |
到着予定時刻が同じ頂点同士は必ずどこかで衝突する。そのため一方の到着予定時刻は 1 遅れる。
たとえばこの例では到着予定時刻が 2 の頂点が 3 つあるので、ひとつを除いて到着予定時刻は 3 になる。
| 到着予定時刻 | 1 | 2 | 3 | 3 | 3 | 3 | 8 |
この議論を何度も行うことにより到着時刻は次のようになる。
| 到着予定時刻 | 1 | 2 | 3 | 4 | 4 | 4 | 8 |
| 到着予定時刻 | 1 | 2 | 3 | 4 | 5 | 5 | 8 |
| 到着予定時刻 | 1 | 2 | 3 | 4 | 5 | 6 | 8 |
到着予定時刻が異なる頂点同士は衝突しないため、8 秒あれば確実にすべてが根に到達できることが分かる。
Educational Codeforces Round 7 E. Ants in Leaves
アリが葉にしかいないのを忘れてて余計なデバッグをしてしまった。
