VO 15 Bài 1 - Cây
Xem dạng PDF
Gửi bài giải
Điểm:
0,57 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
512M
Input:
stdin
Output:
stdout
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
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~.
Bình luận
khong the dung spare table thay the segtree
rmq dc
segment tree nha ae
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
out contest ra.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.