Truy vấn với LCA

Xem PDF

Điểm: 1500 Thời gian: 1.0s Bộ nhớ: 195M 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\)\(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 3
Output
4
1

Bình luận


  • 1
    chienthancontent 8:34 p.m. 17 Tháng 6, 2023 đã chỉnh sửa

    **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


    • 2
      minhtuanitk20 1:43 p.m. 29 Tháng 1, 2022

      có thể giải theo pp range minimium query


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

        Cảm ơn hai bạn T2K30longvu đã 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 phản hồi

        • 9
          T2K30 2:14 p.m. 1 Tháng 7, 2021 chỉnh sửa 9

          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]\)thứ tự dfs của đỉnh \(u\), \(tail[u]\)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]} }\)\({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)\)).

          2 phản hồi

          • 2
            longvu 1:52 p.m. 1 Tháng 7, 2021

            Bài này để giới hạn bộ nhớ thấp là có ý đồ phải ko ạ?


            • -5
              Lê_Gia_Khánh 12:22 p.m. 1 Tháng 7, 2021

              Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.