VOTREE - Cây
Giới hạn- Thời gian: 1.0s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
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.
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. (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.
Output
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
Chú ý:
- Trong thời gian thi, bài của bạn chỉ được chấm với test đề bài.
- Nếu bài của bạn chạy đúng trên máy mình, nhưng sai khi nộp lên SPOJ, bạn có thể kiểm tra ở ideone . Chú ý khi submit lên ideone, để chế độ Secret để người khác không đọc được code của bạn.
Example
Input: 5 3 1 2 2 3 3 4 3 5 2 5 1 3 4 5 Output: 2 1 3
- Người up: voj
- Nguồn bài: VO 2015