問題文中の条件を満たす \(\big((L_1, R_1), (L_2, R_2), \ldots, (L_N, R_N) \big)\) が達成できる \(\max\lbrace L_1, L_2, \ldots, L_N, R_1, R_2, \ldots, R_N \rbrace\) の最小値を考えます。

与えられた木の、葉（すなわち、子を持たない頂点）の個数を \(M\) とし、 \(M\) 個の葉を \(v_1, v_2, \ldots, v_M\) とします。 このとき、

任意の異なる \(2\) つの葉 \(v_i, v_j\) について、 \(S_{v_i} \cap S_{v_j} = \lbrace v_i \rbrace \cap \lbrace v_j \rbrace = \emptyset\)

であるので、問題文中の条件より

任意の異なる \(2\) つの葉 \(v_i, v_j\) について \([L_{v_i}, R_{v_i}] \cap [L_{v_j}, R_{v_j}] = \emptyset\)

でなければなりません。 よって、\(\lbrace L_{v_1}, L_{v_2}, \ldots, L_{v_M} \rbrace\) には少なくとも異なる \(M\) 個の正の整数が含まれなければなりません（ \(\lbrace R_{v_1}, R_{v_2}, \ldots, R_{v_M} \rbrace\) で考えても同様）。 したがって、達成できる \(\max\lbrace L_1, L_2, \ldots, L_N, R_1, R_2, \ldots, R_N \rbrace\) の最小値は \(M\) 以上です。

反対に、\(\max\lbrace L_1, L_2, \ldots, L_N, R_1, R_2, \ldots, R_N \rbrace = M\) は達成できます。 実際、\(\max\lbrace L_1, L_2, \ldots, L_N, R_1, R_2, \ldots, R_N \rbrace = M\) を達成する \(\big((L_1, R_1), (L_2, R_2), \ldots, (L_N, R_N) \big)\) を以下のようにして構成することができます。

1. まず、根である頂点 \(1\) から深さ優先探索を行います。 \(M\) 個の葉について、深さ優先探索で訪れたのが早い順に、 葉 \(1\) 、葉 \(2\) 、\(\ldots\) 、葉 \(M\) とあだ名をつけます。

2. \(i =1, 2, \ldots, N\) について、\(L_i\) と \(R_i\) をそれぞれ頂点 \(i\) の部分木に含まれる葉のあだ名の最小値と最大値とします。

手順 2. で各頂点の部分木に含まれる葉のあだ名の最小値・最大値を求めるのは、深さ優先探索によってまとめて \(\mathrm{O}(N)\) 時間で行えます。

葉のあだ名は深さ優先探索によって与えたので、\(i = 1, 2, \ldots, N\) について、頂点 \(i\) の部分木に含まれる葉のあだ名の集合は、連続するいくつかの整数からなる集合となります。 よって、 頂点 \(i\) の部分木に含まれる葉のあだ名の集合は \([L_i, R_i]\) です。 このことと、葉のあだ名は葉ごとに異なることから、上記の手順で構成した \(\big((L_1, R_1), (L_2, R_2), \ldots, (L_N, R_N) \big)\) がたしかに問題文中の条件を満たすことが確かめられます。

以上より、本問題を \(\mathrm{O}(N)\) 時間で解くことができます。

以下にC++言語による正解例を記載します。

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

int n;
vector<int> G[200005];
int L[200005], R[200005];
int leaf[200005];

int id = 0;
void dfs(int v, int p)
{
  if(v != 1 && G[v].size() == 1){
    leaf[v] = ++id;
    return;
  }
  for(auto u : G[v]) if(u != p) dfs(u, v);
}

void dfs2(int v, int p)
{
  if(leaf[v]){
    L[v] = R[v] = leaf[v];
    return;
  }
  L[v] = 1e9, R[v] = -1e9;
  for(auto u : G[v]){
    if(u == p) continue;
    dfs2(u, v);
    L[v] = min(L[v], L[u]);
    R[v] = max(R[v], R[u]);
  } 
}

int main(void)
{
  cin >> n;
  int u, v;
  for(int i = 1; i <= n-1; i++){
    cin >> u >> v;
    G[u].push_back(v);
    G[v].push_back(u);
  }
  
  dfs(1, -1);
  dfs2(1, -1);
  for(int i = 1; i <= n; i++) cout << L[i] << " " << R[i] << "\n";
  
  return 0;
}