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++, 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

Please read the guidelines before commenting.


  • -2
    pqhxapple  commented on Oct. 16, 2024, 2:59 a.m.

    khong the dung spare table thay the segtree


  • -4
    sitingfake  commented on July 29, 2024, 8:09 a.m.

    segment tree nha ae


  • -20
    trongtenlinhcbhk64  commented on May 27, 2023, 4:02 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • -12
      y  commented on May 28, 2023, 5:01 a.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


      • -23
        trongtenlinhcbhk64  commented on May 31, 2023, 2:42 a.m.

        This comment is hidden due to too much negative feedback. Show it anyway.


        • -2
          y  commented on May 31, 2023, 8:05 a.m.

          out contest ra.


          • -21
            SpiritedAway  commented on June 7, 2023, 1:44 p.m.

            This comment is hidden due to too much negative feedback. Show it anyway.