Dễ dàng nhận thấy sau khi thêm một cạnh nối giữa đỉnh ~i~ và đỉnh ~n+1~ thì đường kính của cây sẽ giữ nguyên hoặc tăng thêm ~1~.

Đường kính của cây sẽ tăng thêm ~1~ nếu như đỉnh ~i~ là đầu mút của bất kì đường kính nào trong cây ban đầu.

Để kiểm tra điều này, tìm hai đầu mút của bất kì đường kính nào trong cây ban đầu bằng thuật toán BFS. Đỉnh ~i~ là đầu mút của một đường kính nào đó nếu như khoảng cách từ đỉnh ~i~ đến một trong hai đầu mút kia bằng độ dài đường kính.

Độ phức tạp thời gian: ~O(n)~

Code tham khảo

#include <bits/stdc++.h>

using namespace std;

const int N = 3e5 + 5;

int n, furthest_node, dist[2][N];
bool vis[N];
vector<int> adj[N];

void bfs(int t, int s) { // Với t là lần chạy bfs, s là đỉnh xuất phát (đỉnh nguồn)
    fill_n(dist[t], n + 1, 0);
    fill_n(vis, n + 1, false);

    queue<int> que;
    que.push(s);
    vis[s] = true;
    while (!que.empty()) {
        int u = que.front(); que.pop();
        for (int v : adj[u]) {
            if (!vis[v]) {
                dist[t][v] = dist[t][u] + 1;
                vis[v] = true;
                que.push(v);

                if (dist[t][v] > dist[t][furthest_node]) {
                    furthest_node = v;
                }
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    bfs(0, 1); 
    bfs(0, furthest_node); // tìm đầu mút thứ nhất
    bfs(1, furthest_node); // tìm đầu mút thứ hai

    int diameter = dist[1][furthest_node];
    for (int i = 1; i <= n; i++) {
        if (max(dist[0][i], dist[1][i]) == diameter) {
            cout << diameter + 1 << "\n";
        } else {
            cout << diameter << "\n";
        }
    }
    cout << "\n";
}