Submit solution
Points:
0.57 (partial)
Time limit:
1.0s
Memory limit:
512M
Input:
stdin
Output:
stdout
Problem source:
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch
Cho cây gồm ~N~ đỉnh ~\left(N \leq 70000\right)~, có gốc ở đỉnh ~1~. Bạn cần trả lời ~Q~ truy vấn, mỗi truy vấn gồm ~2~ số ~u, v~. Bạn cần tìm đỉnh xa gốc nhất, mà là tổ tiên của tất cả các đỉnh ~u, u+1, \ldots, v~.
Input
- Dòng ~1~: Số nguyên dương ~N~ và ~Q~.
- ~N-1~ dòng tiếp theo, mỗi dòng chứa ~2~ số nguyên dương ~u~ và ~v~, thể hiện có ~1~ cạnh nối giữa ~2~ đỉnh ~u~ và ~v~. ~\left(u \ne v;\text{ } 1 \leq u, v \leq N\right)~.
- ~Q~ dòng tiếp theo, mỗi dòng gồm ~2~ số nguyên dương ~u~ và ~v~ ~\left(1 \leq u \leq v \leq N\right)~, thể hiện ~1~ truy vấn.
Output
Với mỗi truy vấn, in ra ~1~ dòng duy nhất là đáp số của truy vấn.
Sample Input
5 3
1 2
2 3
3 4
3 5
2 5
1 3
4 5
Sample Output
2
1
3
Note
- Trong ~30\%~ số test, ~1 \leq N, Q \leq 1000~.
- Trong tất cả các test, ~1 \leq N, Q \leq 70000~.
Comments