User's AC Ratio

66.7% (6/9)

Submission's AC Ratio

42.2% (19/45)

Description

給定一棵樹有 $N$ 個節點,並且有 $M$ 筆查詢,請求出每次查詢 $a, b$ 兩點的最低共同祖先。
請注意:根節點為 $0$

Input Format

第一行有兩個數字 $N, M$
接著有 $N-1$ 行,每行兩個數字 $u_i, v_i$,代表 $u_i, v_i$ 之間有一條邊
在這之後有 $M$ 行,每行兩個數字 $a_i, b_i$,代表要查詢的資料
$N \le 10^ 5, M \le 10 ^ 6$
$0 \le u_i, v_i, a_i, b_i \lt N$

Output Format

對於每一筆查詢輸出 $a_i, b_i$ 的 LCA

Sample Input 1

5 5
4 3
2 3
3 1
2 0
4 2
2 1
0 1
3 0
3 4

Sample Output 1

2
2
0
0
3

Hints

Problem Source

Subtasks

No. Testdata Range Score
1 0~9 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 2500 65536 65536 1
1 2500 65536 65536 1
2 2500 65536 65536 1
3 2500 65536 65536 1
4 2500 65536 65536 1
5 2500 65536 65536 1
6 2500 65536 65536 1
7 2500 65536 65536 1
8 2500 65536 65536 1
9 2500 65536 65536 1