D - 最小共通祖先 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点: 100 点

問題文

1 から N のついた N 個の頂点からなる、頂点 1 を根とする木が与えられます。辺は N-1 個あり、i 番目の辺は頂点 a_i と頂点 b_i を結んでいます。

クエリが Q 回与えられるので、処理してください。i 番目のクエリでは u_i, v_i が与えられるので、u_i と v_i の「最小共通祖先」、すなわち u_i の祖先でも v_i の祖先でもあるものであって、深さが最も深い頂点 p の番号を出力します。

ここで、頂点 x の「祖先」とは、x から根まで親方向にたどったときに通る頂点の集合であり、頂点 x や根も x の祖先に含みます。また、頂点 x の「深さ」とは、x から根まで到達するときに通る辺の個数の最小値とします。根の深さは 0 です。

入力

入力は以下の形式で標準入力から与えられます。

N
a_1 b_1
\vdots
a_{N-1} b_{N-1}
Q
u_1 v_1
\vdots
u_Q v_Q

出力

Q 行出力してください。i 行目では、u_i の祖先でも v_i の祖先でもあるものであって、深さが最も深い頂点 p の番号を出力します。

制約

  • 2 \leq N \leq 100{,}000
  • 1 \leq a_i, b_i \leq N
  • a_i \neq b_i
  • 与えられるグラフは木である
  • 1 \leq Q \leq 100{,}000
  • 1 \leq u_i, v_i \leq N
  • u_i \neq v_i

  • i \neq j ならば \left\{ u_i, v_i \right\} \neq \left\{ u_j, v_j \right\}

入力例 

6
1 2
1 3
2 4
3 5
3 6
3
4 6
5 6
1 5

出力例 

1
3
1

  • 頂点 1 は、頂点 4 の祖先でも頂点 6 の祖先でもある唯一の頂点です。よって、頂点 4, 6 の最小共通祖先は頂点 1 です。
  • 頂点 5 の祖先でも頂点 6 の祖先でもある頂点は頂点 1, 3 の 2 つがありますが、その中で深さが最も深いものは頂点 3 です。よって、頂点 5, 6 の最小共通祖先は頂点 3 です。
  • 頂点 1 は、頂点 1 の祖先でも頂点 5 の祖先でもある唯一の頂点です。よって、頂点 1, 5 の最小共通祖先は頂点 1 です。「頂点 x は頂点 x の祖先である」ことに注意してください。