There are several approaches for this problem; here we will introduce a solution using diameter. (Alternative effective solution is re-rooting DP (Dynamic Programming), although we do not introduce it here.)

Let us regard that each edge of the three has length \(1\), and re-define the distance between vertices \(s\) and \(t\) as the sum of the lengths of the edges in the \(s-t\) path, denoted by \(d(s, t)\).
The diameter of a tree is the longest distance between two vertices in the tree.
Diameters have several good properties, among which the following is closely related to our problem:

Choose any pair of vertices \((s, t)\) distance by the tree’s diameter. (There may be multiple such pairs, but you may choose any.) Then, for each vertex \(u\) in the tree, at least one of \(s\) and \(t\) is a furthest vertex from \(u\). Formally,

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

where \(V\) is the vertex set.

This can be proved by contradiction: if you assume that there exists a vertex \(v\) further from both \(s\) and \(t\), it leads to a contradiction — there will be a path longer than the \(s-t\) path. (For the proof, you need to consider both cases where the \(s-t\) path and \(u-v\) path.)

In this problem, you are asked to find the furthest vertex from each vertex (if there are multiple of them, the one with the largest number). Without the additional “if” condition, you can simply solve it using the property of diameters; but in fact, the property of the diameter can be solved with that condition too.

Consider a new tree (we call it the extended graph) obtained by the following procedure:

• First, add vertices \(1', 2', \dots, N'\) to the original tree.
• Then, for each \(i=1,2,\dots,N\), add an edge of length \(i' \times 10^{-100}\) between vertices \(i\) and \(i'\).

Then we can see that the answer for each vertex \(u\) can be obtained as the furthest vertex from \(u\), with prime removed. In other words, the answer to this problem is the \(v\) satisfying

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

By the construction of the extension graph, the furthest point is unique. Therefore, by the property mentioned above, the furthest vertex is either of the endpoints of the diameter, so once we find the diameter we can also identify the sought \(v\).

Therefore, the problem has been boiled down to finding the diameter and the endpoints of the extension graph. Since the diameter can be found by searching for a furthest vertex twice, this algorithm enables us to solve the problem. The computational complexity is \(\mathrm{O}(N)\).

• Sample code (C++): this code utilizes a concise conclusion obtained by further observations, but we do not describe the details ere as it requires more complex discussions. If you are interest, think about why this implementation works.

#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";
    }
  }
}

• Sample code (Python): you need to choose Codon runtime for the code to be accepted. (If you want to use other runtime like PyPy, in order to find distances on the tree, you need to perform DFS (Depth-First Search) using a stack, for example, instead of using recursive functions.)

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)