VO 15 Bài 1 - Cây

View as PDF

Submit solution


Points: 0.57 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
VO 2015
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

Please read the guidelines before commenting.


There are no comments at the moment.