Submission #70268913

---

Source Code Expand

#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/tag_and_trait.hpp>
using namespace __gnu_pbds;
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
#define rep(i, m, n) for (ll i = (ll)m; i < (ll)n; i++)
#define drep(i, m, n) for (ll i = m - 1; i >= n; i--)
#define Endl endl
#define all(a) a.begin(), a.end()
#define pr(i, j) make_pair(i, j)
#define isin(x, l, r) (l <= x && x < r)
#define chmin(a, b) a = min(a, b)
#define chmax(a, b) a = max(a, b)
#define srt(ar) sort(ar.begin(), ar.end())
#define rev(ar) reverse(ar.begin(), ar.end())
#define jge(f, s, t) cout << (f ? s : t) << endl
template <typename T>
using ordered_set = tree<T, null_type, std::less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#define printar(ar)             \
    do                          \
    {                           \
        for (auto dbg : ar)     \
        {                       \
            cout << dbg << " "; \
        }                       \
        cout << endl;           \
    } while (0)
const ll inf = 1e18;
const ld pi = 3.14159265358979;
const ld eps = 1e-9;
template <class T, ll n, ll idx = 0>
auto make_vec(const ll (&d)[n], const T &init) noexcept
{
    if constexpr (idx < n)
        return std::vector(d[idx], make_vec<T, n, idx + 1>(d, init));
    else
        return init;
}

template <class T, ll n>
auto make_vec(const ll (&d)[n]) noexcept
{
    return make_vec(d, T{});
}
//////////////// 以下を貼る ////////////////
template <class T>
size_t HashCombine(const size_t seed, const T &v)
{
    return seed ^ (std::hash<T>()(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2));
}
/* pair用 */
template <class T, class S>
struct std::hash<std::pair<T, S>>
{
    size_t operator()(const std::pair<T, S> &keyval) const noexcept
    {
        return HashCombine(std::hash<T>()(keyval.first), keyval.second);
    }
};
/* vector用 */
template <class T>
struct std::hash<std::vector<T>>
{
    size_t operator()(const std::vector<T> &keyval) const noexcept
    {
        size_t s = 0;
        for (auto &&v : keyval)
            s = HashCombine(s, v);
        return s;
    }
};
/* tuple用 */
template <int N>
struct HashTupleCore
{
    template <class Tuple>
    size_t operator()(const Tuple &keyval) const noexcept
    {
        size_t s = HashTupleCore<N - 1>()(keyval);
        return HashCombine(s, std::get<N - 1>(keyval));
    }
};
template <>
struct HashTupleCore<0>
{
    template <class Tuple>
    size_t operator()(const Tuple &keyval) const noexcept { return 0; }
};
template <class... Args>
struct std::hash<std::tuple<Args...>>
{
    size_t operator()(const tuple<Args...> &keyval) const noexcept
    {
        return HashTupleCore<tuple_size<tuple<Args...>>::value>()(keyval);
    }
};
////////////////////////////////////////////
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n;
    cin >> n;
    vector<vector<ll>> g(n);
    rep(i, 0, n - 1)
    {
        ll u, v;
        cin >> u >> v;
        u--;
        v--;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    vector<ll> d(n, inf);
    queue<ll> q;
    d[0] = 0;
    q.push(0);
    while (!q.empty())
    {
        ll now = q.front();
        q.pop();
        rep(i, 0, g[now].size())
        {
            ll nxt = g[now][i];
            if (d[nxt] > d[now] + 1)
            {
                d[nxt] = d[now] + 1;
                q.push(nxt);
            }
        }
    }
    ll M = -inf;
    ll x = -1;
    rep(i, 0, n)
    {
        if (d[i] > M)
        {
            M = d[i];
            x = i;
        }
    }
    vector<ll> d2(n, inf);
    d2[x] = 0;
    q.push(x);
    while (!q.empty())
    {
        ll now = q.front();
        q.pop();
        rep(i, 0, g[now].size())
        {
            ll nxt = g[now][i];
            if (d2[nxt] > d2[now] + 1)
            {
                d2[nxt] = d2[now] + 1;
                q.push(nxt);
            }
        }
    }
    M = -inf;
    ll y = -1;
    rep(i, 0, n)
    {
        if (d2[i] > M)
        {
            M = d2[i];
            y = i;
        }
    }
    vector<ll> dia;
    dia.emplace_back(y);
    q.push(y);
    while (!q.empty())
    {
        ll now = q.front();
        q.pop();
        rep(i, 0, g[now].size())
        {
            ll nxt = g[now][i];
            if (d2[nxt] == d2[now] - 1)
            {
                dia.emplace_back(nxt);
                q.push(nxt);
            }
        }
    }
    rev(dia);
    vector<ll> dia_id(n, -1);
    rep(i, 0, dia.size())
    {
        dia_id[dia[i]] = i;
    }
    vector<vector<ll>> ar(dia.size());

    rep(i, 0, dia.size())
    {
        q.push(dia[i]);
        while (!q.empty())
        {
            ll now = q.front();
            if (d2[now] == M || d2[now] == 2 * i)
            {
                ar[i].emplace_back(now);
            }
            q.pop();
            rep(j, 0, g[now].size())
            {
                ll nxt = g[now][j];
                if (dia_id[nxt] == -1)
                {
                    dia_id[nxt] = i;
                    q.push(nxt);
                }
            }
        }
    }
    vector<ll> m(ar.size(), -inf);
    rep(i, 0, ar.size())
    {
        rep(j, 0, ar[i].size())
        {
            chmax(m[i], ar[i][j]);
        }
    }
    vector<ll> m_p(M + 2, -inf), m_s(M + 2, -inf);
    rep(i, 0, M + 1)
    {
        m_p[i + 1] = max(m_p[i], m[i]);
    }
    drep(i, M + 1, 0)
    {
        m_s[i] = max(m_s[i + 1], m[i]);
    }
    rep(i, 0, n)
    {
        ll X = dia_id[i];
        ll ans = -inf;
        if (X >= M - X)
        {
            chmax(ans, m_p[X]);
        }
        if (M - X >= X)
        {
            chmax(ans, m_s[X + 1]);
        }
        cout << ans + 1 << endl;
    }
}

Submission Info

Judge Result