Cho cây gồm N đỉnh, có gốc ở đỉnh 1. (N ≤ 70,000). 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, ..., v.
Dữ liệu vào: VOTREE.INP
+ 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. (u ≠ v, 1 ≤ u, v ≤ N).
+Q dòng tiếp theo, mỗi
dòng gồm 2 số nguyên dương u và v (1 ≤ u ≤ v ≤ N), thể hiện 1 truy vấn.
Dữ liệu ra: Ghi vào tệp văn bản VOTREE.OUT
Với mỗi truy vấn, in ra 1 dòng duy nhất là đáp số của
truy vấn.
Giới hạn:
+ Trong 30% số test, 1 ≤ N, Q ≤ 1000.
+ Trong tất cả các test, 1 ≤ N, Q ≤ 70,000.
+ Thời gian chạy: 1s. Thời gian chạy cho test ví dụ: 0.5s
Ví dụ:
VOTREE.INP
|
VOTREE.OUT
|
5 3
1 2
2 3
3 4
3 5
2 5
1 3
4 5
|
2
1
3
|
Không có nhận xét nào:
Đăng nhận xét