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++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, 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
This comment is hidden due to too much negative feedback. Show it anyway.
This comment is hidden due to too much negative feedback. Show it anyway.
out contest ra.
This comment is hidden due to too much negative feedback. Show it anyway.