Educational Codeforces Round 7 E. Ants in Leaves
解法
0 の子 v の部分木それぞれの葉から, すべてのアリが頂点 v に到達するまで, 何秒かかるかを調べます。
各頂点の v からの距離 d が等しい頂点同士は, 同時に v に向かって行くといつかどこかの頂点でおなじ頂点で重なるので, どちらか一方の頂点のアリは 1 回待たなければなりません。これは, 一方のアリは 1 つ深い頂点から v に向かって行くと解釈しても同じです。
この考えを繰り返すと, 結局すべてのアリは異なる深さから v に向かって進んでいくことになり, すべてのアリが頂点 v に着くまでに何秒かかるのかが一目瞭然です。
vector<int> G[500050]; void dfs(int v, int p, int d, vi& dist) { bool leaf = true; for (int ch : G[v]) { if (ch==p) continue; leaf = false; dfs(ch, v, d+1, dist); } if (leaf) dist.push_back(d); } int main() { cin.tie(0); ios::sync_with_stdio(false); int n; cin >> n; for (int i = 0; i < n-1; i++) { int x, y; cin >> x >> y; x--; y--; G[x].push_back(y); G[y].push_back(x); } int ans = 0; for (int v : G[0]) { vector<int> dist; dfs(v, 0, 0, dist); sort(dist.begin(), dist.end()); int size = dist.size(); for (int i = 0; i < size-1; i++) { dist[i+1] = max(dist[i]+1, dist[i+1]); } ans = max(dist[size-1]+1, ans); } cout << ans << endl; return 0; }