007 - Lowest Common Ancestor
時間制限 1 秒 / メモリ制限 64 MB / 得点 30 / x 1 /
問題
$N$個の頂点を持つ木状のグラフが与えられます。
$Q$個の質問が与えられるので回答を出力してください。
・頂点$x$,頂点$y$の最小共通祖先
最小共通祖先とは頂点1-頂点$x$間の最短経路上にあり、頂点1-頂点$y$間の最短経路上にある、頂点1から最も遠い頂点のことを指す。
入力
入力は以下の形式で標準入力から与えられる。
$N$ $A_1$ $B_1$ $A_2$ $B_2$ : $A_{N-1}$ $B_{N-1}$ $Q$ $x_1$ $y_1$ $x_2$ $y_2$ : $x_Q$ $y_Q$
$A_i,B_i$は辺$i$によって頂点$A_i$と頂点$B_i$がつながっていることを示している。
出力
各質問の答えを改行区切りで出力してください。
出力の最後に改行を入れること。
制約
全ての入出力ケースについて以下を満たす。
- $2 \leq N \leq 10^{4}$
- $1 \leq Q \leq 10^{4}$
- $1 \leq A_i,B_i \leq N$
- $A_i \ne B_i(1 \leq i \leq N)$
- $1 \leq x_i,y_i \leq N$
- $x_i \ne y_i(1 \leq i \leq N)$
- 入力はすべて整数
入出力例
入力例1
6 1 2 1 5 2 3 2 4 5 6 2 3 4 3 6
出力例1
2 1
入力例2
2 1 2 1 1 2
出力例2
1