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

Submit

Status

Ranklist

60 . AB 的祖先