mayoko’s diary

プロコンとかいろいろ。

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