Truy vấn với LCA

Tác giả:

Dạng bài

Điểm: 1500 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho một cái cây có \(n\) nút và ta định nghĩa \(1\) là nút gốc của cây.

Bây giờ ta có \(q\) truy vấn, mỗi truy vấn có dạng: \(l_{i}\) \(r_{i}\) (\(1 \leq l_{i} \leq r_{i} \leq n\)).

Yêu cầu: Ứng với mỗi truy vấn, ta in ra LCA của tất cả các nút từ nút \(l_{i}\) đến nút \(r_{i}\)

Dòng thứ nhất chứa số n (\(2 \leq n \leq 300000\)) - Thể hiện số nút của cây
\(n−1\) dòng tiếp theo, mỗi dòng gồm \(2\) số nguyên \(x,y\) - Thể hiện cạnh nối giữa hai đỉnh \(x\) và \(y\)
Dòng tiếp theo, chứa số \(q\) (\(1 \leq q \leq 300000\)) - Thể hiện số lượng truy vấn
\(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l_{i}\), \(r_{i}\) (\(1 \leq l_{i} \leq r_{i}\leq n\))

Test 1

Input

Output

4
1

Bình luận

4

jumptozero 8:35 p.m. 1 Tháng 7, 2021 ← đã chỉnh sửa →

Cảm ơn hai bạn T2K30 và longvu đã chia sẻ solutions ! Hai bạn có thể kết hợp với nhau viết solutions thật đầy đủ để mọi người cùng theo dõi nhé ! BQT sẽ xem xét và add vào Editorial nhé !

1

jalsol 12:33 p.m. 2 Tháng 7, 2021 ← đã chỉnh sửa →

anh ơi khi nào mới có editorial vậy ạ ;-; bài khó quá huhu