Truy vấn với LCA
Xem PDF
Đ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}\)
Input
-
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\))
Output
- Ứng với mỗi truy vấn, in ra đáp án cần tìm.
Scoring
- Subtask \(1\) (\(40\%\) số điểm): \(2 \leq n,q \leq 20\).
- Subtask \(2\) (\(60\%\) số điểm): Không có ràng buộc gì thêm.
Example
Test 1
Input
5
1 4
2 5
3 5
2 4
2
2 4
1 3Output
4
1
Bình luận
daj cho e hỏi là sao e chạy bình thường đúng hết test nma sao khi nộp lại bị runtime error v ạ
**Lưu ý: Code chỉ mang tính chất tham khảo nếu đọc sol của bạn T2K30 và bạnlongvu mà không hiểu
Code theo RMQ: https://ideone.com/p3zVXA
có thể giải theo pp range minimium query
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é !
Spoiler Alert
Mình xin đóng góp cách giải như sau 😊
Segment Tree
Ta thấy \(lca(a,b,c) = lca(a,lca(b,c))\).
Mỗi truy vấn ta chỉ cần tính \(lca\) của các đỉnh có số thứ tự liên tiếp nên ta có thể lưu lca của cả đoạn để dùng lại. Ví dụ ta lưu các \(lca\) trong từng node của segment tree. Xét một cây có \(n = 6\) đỉnh, ta xây dựng cây phân đoạn như sau
Mỗi nút \([l, r]\) chứa \(lca(l,l+1,...,r)\). Trong ví dụ trên, \(lca(2,3,...,5)\) bằng \(lca([2],[3],[4,5])\).
Độ phức tạp \(O\left( {{{\log }^2}n} \right)\) mỗi truy vấn, build mất \(O\left( {n{{\log }^2}n} \right)\), mình nghĩ là đủ để AC vì máy chấm của LQDOJ rất khỏe :))).
Ở dưới mình sẽ bàn về cách tối ưu hơn.
RMQ
Gọi \(num[u]\) là thứ tự dfs của đỉnh \(u\), \(tail[u]\) là thứ tự thoát dfs của đỉnh u. Như vậy đỉnh \(u\) là tổ tiên của đỉnh \(v\) khi và chỉ khi \(num[u] \le num[v{\rm{]}} \le tail{\rm{[}}u]\) (1).
Với mỗi truy vấn \((l,r)\), ta xét 2 đỉnh \(u\), \(v\) thỏa mãn \({num[u] = \min \mathop {num[i]}\limits_{i \in \left[ {l,r} \right]} }\) và \({num[v{\rm{]}} = \max \mathop {num[i]}\limits_{i \in \left[ {l,r} \right]} }\).
Từ đó ta có \(num[u] \le num[i] \le num[v{\rm{]}}\) \(\forall i \in \left[ {l,r} \right]\) (2).
Gọi \(x = lca(u,v)\). Từ (1) và (2) \(\Rightarrow num[x{\rm{]}} \le {\rm{num[u]}} \le {\rm{num[i]}} \le {\rm{num[v]}} \le {\rm{tail[x]}}\) \(\forall i \in \left[ {l,r} \right]\) (3).
Từ (1) và (3) suy ra \(x\) là tổ tiên của tất cả các đỉnh trong đoạn \([l,r]\)! Kết quả của bài toán chính là \(x\)!
Ví dụ:
Độ phức tạp \(O(\log n)\) cho mỗi truy vấn (mất 3 \(log\), 1 tìm u, 1 tìm v, 1 tìm \(lca(u,v)\)).
Bài này để giới hạn bộ nhớ thấp là có ý đồ phải ko ạ?
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.