提出 #70261263

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;

#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define fix(x) fixed << setprecision(x)
#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
#define repe(i, start, end) for (auto i = (start); (i) <= (end); (i)++)
#define rrep(i, start, end) for (auto i = (start); (i) >= (end); (i)--)

constexpr auto PI = 3.14159265358979;
constexpr int INF = 1e+9;
constexpr long long INFL = 1e+18;

using ll = long long;
using lld = long double;
// using mint = modint1000000007;
using mint = modint998244353;
using Pair_int = pair<int, int>;
using Pair_ll = pair<ll, ll>;
template <class T>
using Graph = vector<vector<T>>;

template <class T1, class T2>
inline auto div_floor(T1 a, T2 b)
{
    if (b < 0)
        a *= -1, b *= -1;
    if (a >= 0)
        return a / b;
    else
        return (a + 1) / b - 1;
}
template <class T1, class T2>
inline auto div_ceil(T1 a, T2 b)
{
    if (b < 0)
        a *= -1, b *= -1;
    if (a <= 0)
        return a / b;
    else
        return (a - 1) / b + 1;
}
ll pow_int(ll x, ll n)
{
    ll res = 1;
    while (n > 0)
    {
        if (n & 1)
            res *= x;
        x *= x;
        n >>= 1;
    }
    return res;
}
ll pow_mod(ll x, ll n, ll mod)
{
    ll res = 1;
    while (n > 0)
    {
        if (n & 1)
            res = res * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return res;
}
ll gcd(ll x, ll y)
{
    if (x < y)
        swap(x, y);
    ll r;
    while (y > 0)
    {
        r = x % y;
        x = y;
        y = r;
    }
    return x;
}
ll lcm(ll x, ll y) { return ll(x / gcd(x, y)) * y; }
ll nCk(ll n, ll r)
{
    if (r < 0 || n < r)
        return 0;
    ll ans = 1;
    for (ll i = 1; i <= r; i++)
    {
        ans *= n--;
        ans /= i;
    }
    return ans;
}
int get_rand(int seed, int min, int max)
{
    static mt19937_64 mt64(seed);
    uniform_int_distribution<int> get_rand_int(min, max);
    return get_rand_int(mt64);
}
template <typename T>
inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); }
template <typename T>
inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); }
template <class T1, class T2>
inline auto mod(T1 x, T2 r) { return (x % r + r) % r; }

// ======================================== //

int main()
{
    int N;
    cin >> N;
    Graph<int> G(N);
    rep(i, 0, N - 1)
    {
        int A, B;
        cin >> A >> B;
        A--, B--;
        G[A].push_back(B);
        G[B].push_back(A);
    }

    auto get_dist = [&](int start) -> vector<int>
    {
        vector<int> res(N, -1);

        auto dfs = [&](auto &self, int now, int parent, int d) -> void
        {
            res[now] = d;
            for (auto next : G[now])
            {
                if (next == parent)
                    continue;

                self(self, next, now, d + 1);
            }
            return;
        };

        dfs(dfs, start, -1, 0);
        return res;
    };

    auto get_farthest = [&](const vector<int> &dist) -> int
    {
        int res = -1;
        int max_dist = -1;
        rep(i, 0, N)
        {
            if (dist[i] > max_dist)
            {
                res = i;
                max_dist = dist[i];
            }
            else if (dist[i] == max_dist)
            {
                chmax(res, i);
            }
        }

        return res;
    };

    vector<int> dist_0 = get_dist(0);
    int u = get_farthest(dist_0);

    vector<int> dist_u = get_dist(u);
    int w = get_farthest(dist_u);

    vector<int> dist_w = get_dist(w);

    rep(v, 0, N)
    {
        int from_u = dist_u[v];
        int from_w = dist_w[v];

        if (from_u == from_w)
        {
            cout << max(u, w) + 1 << endl;
        }
        else if (from_u < from_w)
        {
            cout << w + 1 << endl;
        }
        else
        {
            cout << u + 1 << endl;
        }
    }

    return 0;
}

提出情報

ジャッジ結果