この問題はいくつかの解き方がありますが、ここでは木の 直径 を利用した解法を説明します。(解説はしませんが全方位木 DP を利用した解法も有力でしょう)

以降では木の辺は長さ \(1\) の辺であるとみなして、頂点 \(s\) と頂点 \(t\) の距離を「\(s-t\) パスに含まれる辺の長さの総和」として定義し直します。そしてこれを \(d(s, t)\) と表します。
木の直径とは、木に含まれる頂点のうち最も離れている \(2\) 頂点の距離のことを言います。
木の直径はいくつかの良い性質を持ちますが、次の性質が今回の問題と密接に関わっています。

2 点間の距離が直径と一致するような頂点の組を選び \((s, t)\) とする。(候補は複数ある場合は自由に 1 組選んでよい) この時、木に含まれる任意の頂点 \(u\) について、\(s\) と \(t\) の少なくとも一方が \(u\) から最も遠い頂点である。言い換えると、頂点集合を \(V\) とした時に

\[\max_{v \in V} d(u, v) = \max \lbrace d(u, s), d(u, t) \rbrace\]

が成り立つ。

証明は背理法を利用すればよいです。すなわち、頂点 \(v\) であって \(s, t\) よりも \(u\) から遠い頂点があると仮定して、矛盾、すなわち \(s-t\) パスよりも長いパスの存在を導けばよいです。(\(s-t\) パスと \(u-v\) パスの交点の有無で場合分けをすることになります。)

今回の問題は「各頂点から最も遠い頂点(ただし複数ある場合は番号が最も大きい頂点)」を求める問題です。括弧内が無ければ直径の性質をそのまま利用すれば解くことができますが、実は括弧がついていても直径の性質を応用することで解くことが出来ます。

以下の手順で元の木を拡張した新たな木(拡張グラフと呼びます)を考えます。

• まず、元の木に頂点 \(1', 2', \dots, N'\) を追加する。
• そして、\(i=1,2,\dots,N\) について、頂点 \(i\) と頂点 \(i'\) の間に長さ \(i' \times 10^{-100}\) の辺を貼る。

すると、各頂点 \(u\) に対する今回の問題の答えはこの拡張グラフ上での \(u\) からの最遠点の番号からダッシュを取り除いたものとなっていることが確認できます。すなわち、

\[\argmax_{1 \leq v \leq N} d(u, v')\]

を満たす \(v\) が今回の問題の答えとなります。また、拡張グラフの作り方から拡張グラフ上の最遠点は一意に定まります。よって、先に挙げた性質から、木上で最も遠い頂点は直径の両端のいずれかなので、直径がわかれば上式を満たす \(v\) がわかることになります。

よって今回の問題は拡張グラフ上の直径およびその両端点を求める問題に帰着しました。直径は最遠点の計算を \(2\) 回行えば計算できることが知られているので、そのアルゴリズムを用いれば今回の問題を解くことが出来ます。計算量は \(\mathrm{O}(N)\) で十分高速です。

• 実装例(C++) 説明しようとすると踏み込んだ議論が必要となるので詳細は省略しますが、実装例では解説よりもさらに考察を深めることで簡潔な結論を得た上で実装しています。興味がある人はなぜこの実装で上手くいくのか考えてみましょう。

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int N;
  cin >> N;
  vector<vector<int>> g(N);
  for (int i = 0; i < N - 1; i++) {
    int A, B;
    cin >> A >> B;
    --A, --B;
    g[A].push_back(B);
    g[B].push_back(A);
  }

  auto calc_dist = [&](int root) {
    vector<int> dist(N, -1);
    queue<int> Q;
    Q.push(root), dist[root] = 0;
    while (!Q.empty()) {
      int c = Q.front();
      Q.pop();
      for (int d : g[c]) {
        if (dist[d] != -1) continue;
        Q.push(d), dist[d] = dist[c] + 1;
      }
    }
    return dist;
  };

  auto d0 = calc_dist(0);
  int u = N - 1;
  for (int i = N - 2; i >= 0; i--) {
    if (d0[i] > d0[u]) u = i;
  }
  auto du = calc_dist(u);
  int v = N - 1;
  for (int i = N - 2; i >= 0; i--) {
    if (du[i] > du[v]) v = i;
  }
  auto dv = calc_dist(v);

  for (int i = 0; i < N; i++) {
    if (du[i] > dv[i]) {
      cout << u + 1 << "\n";
    } else if (du[i] == dv[i]) {
      cout << max(u, v) + 1 << "\n";
    } else {
      cout << v + 1 << "\n";
    }
  }
}

• 実装例(Python) このコードで AC するには処理系に codon を選ぶ必要があります。(PyPy などで通す場合は再帰関数を用いた DFS で木の距離を求めているところを stack を用いた DFS などに置き換える必要があります。)

def dfs(c, depth, dist):
    dist[c] = depth
    for d in g[c]:
        if dist[d] != -1:
            continue
        dfs(d, depth + 1, dist)


N = int(input())
g = [[] for _ in range(N)]
for i in range(N - 1):
    u, v = [int(i) for i in input().split()]
    g[u - 1].append(v - 1)
    g[v - 1].append(u - 1)

d0 = [-1] * N
dfs(0, 0, d0)
u = max([(d0[i], i) for i in range(N)])[1]
du = [-1] * N
dfs(u, 0, du)
v = max([(du[i], i) for i in range(N)])[1]
dv = [-1] * N
dfs(v, 0, dv)

for i in range(N):
    print(max((du[i], u), (dv[i], v))[1] + 1)