給定一棵樹有 $N$ 個節點,並且有 $M$ 筆查詢,請求出每次查詢 $a, b$ 兩點的最低共同祖先。
請注意:根節點為 $0$
第一行有兩個數字 $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$
對於每一筆查詢輸出 $a_i, b_i$ 的 LCA
No. | Testdata Range | Score |
---|---|---|
1 | 0~9 | 100 |
No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
---|---|---|---|---|
0 | 2500 | 65536 | 65536 | |
1 | 2500 | 65536 | 65536 | |
2 | 2500 | 65536 | 65536 | |
3 | 2500 | 65536 | 65536 | |
4 | 2500 | 65536 | 65536 | |
5 | 2500 | 65536 | 65536 | |
6 | 2500 | 65536 | 65536 | |
7 | 2500 | 65536 | 65536 | |
8 | 2500 | 65536 | 65536 | |
9 | 2500 | 65536 | 65536 |