Submission #70304232

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <deque>
#include <queue>
#include <numeric>
#include <stack>
#include <cassert>
#include <cstring>
#include <cmath>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <chrono>
#include <sstream>
#include <limits>
#include <functional>
using namespace std;
#define endl '\n'
// #define LOCAL

using int64 = int64_t;
using uint64 = unsigned long long;
using int128 = __int128_t;

#ifdef LOCAL
#include "src/debug.h"
#else
#define debug(...) 42
#endif

// tree diameter
const int INF = numeric_limits<int>::max();
int N;
vector<vector<int>> adj;

vector<int> bfs(int src) {
    vector<int> dist(N, INF);
    dist[src] = 0;
    queue<int> q;
    q.emplace(src);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : adj[u]) {
            if (dist[v] == INF) {
                dist[v] = dist[u] + 1;
                q.emplace(v);
            }
        }
    }
    return dist;
}

void solve() {
    cin >> N;
    adj.assign(N, vector<int>());
    for (int i = 0; i < N - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
    // find farthest from node 0
    vector<int> d0 = bfs(0);
    int u = -1, maxd = -1; // handles tie break by taking larger node index
    for (int i = N - 1; i >= 0; --i) {
        if (d0[i] > maxd) {
            maxd = d0[i];
            u = i;
        }
    }
    vector<int> du = bfs(u);
    int v = -1, maxd2 = -1;
    for (int i = N - 1; i >= 0; --i) {
        if (du[i] > maxd2) {
            maxd2 = du[i];
            v = i;
        }
    }
    vector<int> dv = bfs(v);
    if (u < v) {
        swap(u, v);
        swap(du, dv);
    }
    // farthest distance from every node i
    // u is taken on ties
    for (int i = 0; i < N; ++i) {
        if (du[i] >= dv[i]) {
            cout << u + 1 << endl;
        } else {
            cout << v + 1 << endl;
        }
    }
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}

Submission Info

Judge Result