LCA: tổ tiên chung gần nhất bằng nâng nhị phân

Tổ tiên chung gần nhất là đỉnh nào?

Trong cây có gốc, cha của một đỉnh là đỉnh đứng ngay trước nó trên đường từ gốc tới đỉnh đó. Đi lên nhiều lần cho ta các tổ tiên. Hai đỉnh luôn có ít nhất một tổ tiên chung là gốc; LCA chọn tổ tiên chung có độ sâu lớn nhất, tức nằm gần hai đỉnh nhất theo quan hệ đi lên.

Xét gốc 0 có con 1,2; đỉnh 1 có con 3,4; đỉnh 2 có con 5,6. LCA(3,4)=1 vì hai nhánh gặp nhau ở 1. LCA(3,6)=0 vì một đỉnh thuộc nhánh trái và một thuộc nhánh phải. LCA(2,6)=2, bởi một đỉnh có thể là tổ tiên của đỉnh còn lại.

LCA không yêu cầu cây nhị phân. Một đỉnh có thể có bao nhiêu con cũng được. Hình nhị phân chỉ giúp dễ nhìn. Điều cần thiết cho cách cài ở đây là dữ liệu thật sự là cây liên thông, không chu trình, cùng một gốc được chọn cho toàn bộ truy vấn.

Cách chậm: đi từng cha một

Nếu hai đỉnh khác độ sâu, nâng đỉnh sâu hơn tới khi bằng nhau. Sau đó nâng cả hai mỗi lần một cạnh; khi chúng bằng nhau thì đó là LCA. Cách này đúng vì các đường lên gốc trong cây không thể tách ra sau khi đã gặp nhau.

Trên một cây dài như dây, mỗi truy vấn có thể cần O(n) bước. Với nhiều truy vấn, lặp lại việc đi qua từng cha trở nên tốn kém. Nâng nhị phân giữ nguyên ý tưởng đi lên, nhưng gộp nhiều cạnh thành một lần tra bảng.

Đây là cải tiến cho trường hợp nhiều truy vấn trên cùng một cây tĩnh. Nếu chỉ có một câu hỏi và cây nhỏ, cách đi từng cha hoặc một lượt duyệt riêng có thể đơn giản hơn. Không phải mọi bài nhắc tới tổ tiên đều bắt buộc dựng bảng O(n log n).

Bảng up[u][j] lưu tổ tiên cách 2 mũ j cạnh

Đặt up[u][0] là cha trực tiếp của u. Với j lớn hơn 0, nhảy 2 mũ j cạnh bằng hai lần nhảy 2 mũ (j−1), nên up[u][j]=up[up[u][j−1]][j−1]. Code đặt cha của gốc bằng chính gốc, vì thế nhảy quá cao vẫn dừng ở gốc mà không truy cập chỉ số −1.

Với cây ví dụ, up[3][0]=1, up[3][1]=0; up[6][0]=2, up[6][1]=0. Đỉnh 3 sâu 2, nên bước nhảy 2 cạnh đưa thẳng về gốc. Bảng cũng được điền cho gốc: mọi cột đều bằng 0.

Số cột phải đủ biểu diễn độ sâu lớn nhất. Code lấy theo độ dài bit của n, bảo đảm có cả trường hợp n=1. Khi tự dùng một hằng LOG, hãy kiểm cây dài nhất được đề cho, đặc biệt ở ngay trước hoặc sau một lũy thừa của 2.

Bước một: cân bằng độ sâu bằng các bit

Giả sử u sâu hơn v một lượng diff. Viết diff thành tổng các lũy thừa của 2 rồi dùng các cột tương ứng của up. Nếu diff=13=8+4+1, chỉ cần ba lần nhảy thay vì 13 lần đi cha. Các bit 1 trong biểu diễn nhị phân cho biết phải lấy những bước nào.

Sau khi cân bằng, nếu u bằng v thì trả luôn. Trường hợp một đỉnh là tổ tiên của đỉnh còn lại được xử lý ở đây. Ví dụ LCA(2,6): nâng 6 lên một cạnh thành 2, hai đỉnh gặp nhau nên kết quả là 2.

Nếu bỏ bước cân bằng rồi nâng hai đỉnh cùng lúc, bạn có thể cho một đỉnh vượt qua tổ tiên cần tìm trong khi đỉnh kia vẫn ở dưới. Hai trạng thái phải ở cùng độ sâu trước khi sử dụng bước nâng đồng thời.

Bước hai: nâng cùng lúc nhưng chưa cho gặp

Xét j từ lớn xuống nhỏ. Nếu up[u][j] khác up[v][j], có thể nâng cả hai tới các tổ tiên đó: chúng vẫn nằm ở hai nhánh khác nhau, chưa vượt qua chỗ gặp. Nếu hai tổ tiên bằng nhau, không nhảy bước đó vì nó có thể đi tới LCA hoặc cao hơn và làm mất vị trí ngay dưới điểm gặp.

Sau khi xét đủ các cột, u và v khác nhau nhưng có chung cha trực tiếp. Trả up[u][0]. Với cặp 3,6 trong hình, tổ tiên cách 2 cạnh của cả hai là 0 nên không nhảy; tổ tiên cách 1 cạnh là 1 và 2 khác nhau nên nhảy tới 1,2. Cha chung của chúng là 0.

Với cặp 3,4, tổ tiên cách 1 cạnh đã bằng nhau là 1. Không nhảy; kết thúc trả cha của 3 là 1. Hai ví dụ cho thấy thuật toán cố dừng ngay dưới LCA, chứ không nhảy một bước lớn đầu tiên miễn là hai đỉnh đi được.

Code C++ và Python

#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
class LCA{
    vector<vector<int>> up;
    int lg;
public:
    vector<int> depth;
    LCA(const vector<vector<int>>& g,int root):depth(g.size(),-1){
        int n=g.size();lg=1;while((1LL<<lg)<=n)++lg;
        up.assign(n,vector<int>(lg,root));
        vector<int> st={root};depth[root]=0;
        while(!st.empty()){
            int u=st.back();st.pop_back();
            for(int v:g[u])if(depth[v]==-1){
                depth[v]=depth[u]+1;up[v][0]=u;st.push_back(v);
            }
        }
        for(int j=1;j<lg;++j)for(int u=0;u<n;++u)
            up[u][j]=up[up[u][j-1]][j-1];
    }
    int query(int u,int v)const{
        if(depth[u]<depth[v])swap(u,v);
        int diff=depth[u]-depth[v];
        for(int j=0;j<lg;++j)if((diff>>j)&1)u=up[u][j];
        if(u==v)return u;
        for(int j=lg-1;j>=0;--j)if(up[u][j]!=up[v][j]){
            u=up[u][j];v=up[v][j];
        }
        return up[u][0];
    }
    int distance(int u,int v)const{return depth[u]+depth[v]-2*depth[query(u,v)];}
};
int main(){
    int n=7,q=4,root=0;
    vector<pair<int,int>> e={{0,1},{0,2},{1,3},{1,4},{2,5},{2,6}};
    vector<pair<int,int>> ask={{3,4},{3,6},{2,6},{0,0}};
    if(cin>>n>>q>>root){
        e.resize(n-1);for(auto& [u,v]:e)cin>>u>>v;
        ask.resize(q);for(auto& [u,v]:ask)cin>>u>>v;
    }
    vector<vector<int>> g(n);
    for(auto [u,v]:e){g[u].push_back(v);g[v].push_back(u);}
    LCA a(g,root);
    for(auto [u,v]:ask)cout<<a.query(u,v)<<' '<<a.distance(u,v)<<'\n';
}

import sys

class LCA:
    def __init__(self,g,root):
        n=len(g);self.lg=max(1,n.bit_length())
        self.up=[[root]*self.lg for _ in range(n)]
        self.depth=[-1]*n;self.depth[root]=0
        stack=[root]
        while stack:
            u=stack.pop()
            for v in g[u]:
                if self.depth[v]==-1:
                    self.depth[v]=self.depth[u]+1
                    self.up[v][0]=u;stack.append(v)
        for j in range(1,self.lg):
            for u in range(n):
                self.up[u][j]=self.up[self.up[u][j-1]][j-1]

    def query(self,u,v):
        if self.depth[u]<self.depth[v]:
            u,v=v,u
        diff=self.depth[u]-self.depth[v]
        for j in range(self.lg):
            if (diff>>j)&1:
                u=self.up[u][j]
        if u==v:
            return u
        for j in range(self.lg-1,-1,-1):
            if self.up[u][j]!=self.up[v][j]:
                u=self.up[u][j];v=self.up[v][j]
        return self.up[u][0]

    def distance(self,u,v):
        return self.depth[u]+self.depth[v]-2*self.depth[self.query(u,v)]

if __name__=='__main__':
    a=list(map(int,sys.stdin.buffer.read().split()))
    n=7;root=0;edges=[(0,1),(0,2),(1,3),(1,4),(2,5),(2,6)]
    ask=[(3,4),(3,6),(2,6),(0,0)]
    if a:
        n,q,root=a[:3];i=3
        edges=[tuple(a[i+2*j:i+2*j+2]) for j in range(n-1)];i+=2*(n-1)
        ask=[tuple(a[i+2*j:i+2*j+2]) for j in range(q)]
    g=[[] for _ in range(n)]
    for u,v in edges:
        g[u].append(v);g[v].append(u)
    tree=LCA(g,root)
    for u,v in ask:
        print(tree.query(u,v),tree.distance(u,v))

Không nhập thì chương trình trả bốn dòng, mỗi dòng là LCA rồi số cạnh trên đường đi: (3,4) cho 1 2, (3,6) cho 0 4, (2,6) cho 2 1, (0,0) cho 0 0. Input riêng bắt đầu n, q, root; sau đó n−1 cạnh vô hướng và q cặp truy vấn.

Điều kiện đầu vào là n dương, cây liên thông không chu trình, root và các nhãn đỉnh hợp lệ. Code xây mảng cha và độ sâu bằng ngăn xếp lặp rồi điền bảng nhảy dưới giả thiết dữ liệu đầu vào đã là một cây hợp lệ. Nếu đưa đồ thị rời rạc hoặc có chu trình, các giá trị thu được không có bảo đảm LCA theo mô hình đang học.

Trong C++, bảng được lưu theo đỉnh rồi cột; Python cũng dùng các hàng độc lập. Không khởi tạo các hàng bằng việc nhân một list bên trong, vì thay bảng của một đỉnh có thể làm đổi nhiều hàng. Số cột phụ thuộc n nên không cần tự đoán một hằng cố định.

Tính khoảng cách và thay đổi gốc

Đường giữa u và v đi từ u lên LCA rồi xuống v. Số cạnh đoạn đầu là depth[u]−depth[lca], đoạn sau là depth[v]−depth[lca]. Cộng lại được công thức trong khối ý chính. Với 3,6, độ sâu hai đầu đều 2 và LCA sâu 0 nên khoảng cách là 4.

Nếu cây có trọng số, depth đếm cạnh không đủ để tính tổng trọng số. Lưu thêm tổng trọng số từ gốc tới mỗi đỉnh, rồi thay depth trong công thức khoảng cách bằng tổng đó. Phần truy vấn LCA vẫn dựa trên độ sâu theo số cạnh để nâng đúng tổ tiên.

Đổi gốc có thể đổi LCA dù đường vô hướng giữa hai đỉnh không đổi. Chẳng hạn trên chuỗi 0–1–2, gốc 0 cho LCA(0,2)=0, còn gốc 2 cho kết quả 2. Code này tiền xử lý cho một gốc cố định; nếu đề thay gốc liên tục, cần kỹ thuật truy vấn phù hợp hoặc công thức mở rộng đã chứng minh.

Độ phức tạp và các bài không cùng mô hình

Xây cha, depth tốn O(n); điền bảng cần O(n log n) thời gian và bộ nhớ. Mỗi query đi qua số cột O(log n). Hàm distance trong code gọi query để xác định LCA nên vẫn O(log n). Nếu một truy vấn cần cả LCA và khoảng cách, có thể lưu kết quả LCA vừa tính để tránh gọi lại, không đổi cận.

LCA trên cây tìm kiếm nhị phân có thể dùng thứ tự khóa để đi từ gốc mà không cần bảng nhảy. LCA trên cây nhị phân chỉ hỏi một lần có thể dùng DFS trả kết quả lên. Bài biết sẵn con trỏ cha lại có cách đi lên riêng. Chúng chia sẻ khái niệm tổ tiên chung, nhưng không có cùng định dạng dữ liệu hoặc yêu cầu tiền xử lý.

Kiểm với cách đi cha chậm

Để tự kiểm tra trên các cây nhỏ sinh ngẫu nhiên, bạn có thể viết thêm một hàm nhảy từng bước cha một (u = up[0][u]) cho tới khi hai đỉnh gặp nhau, rồi đối chiếu cả đỉnh LCA lẫn khoảng cách với hàm nâng nhị phân.

Các kích thước gồm 1,2,3,31,32,33 để bắt lỗi số cột ở biên lũy thừa hai. Khi tự kiểm thêm, dùng cây dây, cây sao, hai đỉnh giống nhau, một đỉnh là gốc và một đỉnh là tổ tiên của đỉnh còn lại. Những trường hợp này bắt lỗi cân bằng độ sâu và điều kiện trả sớm rất hiệu quả.

Luyện ngay trên Big-O Coding

Bài nâng nhị phân luyện trực tiếp nhiều truy vấn trên cây. Hai bài còn lại dùng cây nhị phân và cây tìm kiếm nhị phân. Chúng cùng hỏi tổ tiên chung nhưng có thể khai thác cấu trúc hoặc thứ tự khóa khác nhau; cần đọc định dạng và chọn cách biểu diễn phù hợp, không chép nguyên phần nhập danh sách cạnh vào một bài chấm hàm.

Câu hỏi thường gặp

Nguồn tham khảo

• CP-Algorithms: LCA binary lifting
• Open Data Structures: Basic Binary Tree
• C++ reference: vector