Save Nagato

    1#include <bits/stdc++.h>
    2using namespace std;
    3 
    4pair<int, vector<int>> bfs(int start, const vector<vector<int>> &g){
    5    int n = g.size() - 1;
    6    vector<int> d(n + 1, -1);
    7    queue<int> q;
    8    d[start] = 0; q.push(start);
    9    int far = start;
    10    while(!q.empty()){
    11        int u = q.front(); q.pop();
    12        if(d[u] > d[far]) far = u;
    13        for(int v : g[u]){
    14            if(d[v] == -1){
    15                d[v] = d[u] + 1;
    16                q.push(v);
    17            }
    18        }
    19    }
    20    return {far, d};
    21}
    22 
    23int main(){
    24    ios::sync_with_stdio(0);
    25    cin.tie(0);
    26    int n; cin >> n;
    27    vector<vector<int>> g(n + 1);
    28    for(int i = 0; i < n - 1; i++){
    29        int u, v; cin >> u >> v;
    30        g[u].push_back(v);
    31        g[v].push_back(u);
    32    }
    33    if(n == 1){
    34        cout << 1 << "\n";
    35        return 0;
    36    }
    37    //farthest from 1 -> A
    38    auto [A, d1] = bfs(1, g);
    39    //farthest from A -> B, also get dist from A
    40    auto tmp = bfs(A, g);
    41    int B = tmp.first;
    42    vector<int> distA = move(tmp.second);
    43    //dist from B
    44    auto tmp2 = bfs(B, g);
    45    vector<int> distB = move(tmp2.second);
    46    // For each node v, answer = max(distA[v], distB[v]) + 1
    47    for(int v = 1; v <= n; v++){
    48        cout << max(distA[v], distB[v]) + 1 << "\n";
    49    }
    50    return 0;
    51}
    52