Truy vấn với LCA

Xem PDF
Tác giả:
jumptozero
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}\)

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 3
Output 
4
1

Bình luận


  • 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]\) 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)\)).


    • -16
      Lê_Gia_Khánh    8:35 a.m. 2 Tháng 7, 2021 ← chỉnh sửa 3

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


      • 5
        longvu    3:23 p.m. 1 Tháng 7, 2021 ← đã chỉnh sửa

        Mình góp ý thêm 1 cách giải nữa đó là: Nếu các bạn biết, ta có thể tìm LCA bằng Euler tour thì khi tìm LCA(u, v) là tìm giá trị nhỏ nhất từ vị trí đầu tiên của nút u đến vị trí đầu tiên của v trong mảng Euler tour. Mà trong mảng Euler tour ta nhận thấy các nút nằm trong đoạn từ vị trí xuất hiện đầu tiên của u đến vị trí xuất hiện cuối cùng của u sẽ cai quan toàn bộ các nút cây con gốc u. Khi tìm LCA của nhiều nút ta chỉ cần tìm ra gốc của 1 cây con bao trùm tất cả các nút đấy. Vì vậy khi tìm LCA trong bài này ta chỉ cần tìm LCA của 2 vị trí xuất hiện đầu tiên lớn nhất và nhỏ nhất trong mảng Euler tour của các nút từ [L, R]. T có thể dùng segment tree giải quyết vấn đề này nhưng các bạn lưu ý cần khéo léo 1 chút trong cách cài đặt segment tree để khỏi bị MLE =))


        • 4
          T2K30    3:29 p.m. 1 Tháng 7, 2021 ← chỉnh sửa 2

          cách tiếp cận của bạn hay vậy, thanks :))

        5 bình luận nữa