LCA (Lowest Common Ancestor)

เทคนิคการหา Lowest Common Ancestor ของสอง nodes ใน tree

Lowest Common Ancestor (LCA)

LCA ของ nodes $u$ และ $v$ คือ node ที่อยู่ลึกที่สุดที่เป็น ancestor ของทั้ง $u$ และ $v$

วิธีที่ 1: Binary Lifting

Preprocess ใน $O(n \log n)$ , Query ใน $O(\log n)$

Implementation

const int LOG = 20;

class LCA {
    int n;
    vector<vector<int>> adj;
    vector<vector<int>> up;
    vector<int> depth;
    
public:
    LCA(int n) : n(n), adj(n), up(n, vector<int>(LOG, -1)), depth(n) {}
    
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    void build(int root = 0) {
        function<void(int, int, int)> dfs = [&](int u, int p, int d) {
            up[u][0] = p;
            depth[u] = d;
            
            for (int j = 1; j < LOG; j++) {
                if (up[u][j-1] != -1) {
                    up[u][j] = up[up[u][j-1]][j-1];
                }
            }
            
            for (int v : adj[u]) {
                if (v != p) {
                    dfs(v, u, d + 1);
                }
            }
        };
        
        dfs(root, -1, 0);
    }
    
    int getAncestor(int v, int k) {
        for (int j = 0; j < LOG && v != -1; j++) {
            if (k & (1 << j)) {
                v = up[v][j];
            }
        }
        return v;
    }
    
    int query(int u, int v) {
        // Make u the deeper node
        if (depth[u] < depth[v]) swap(u, v);
        
        // Bring u to the same depth as v
        u = getAncestor(u, depth[u] - depth[v]);
        
        if (u == v) return u;
        
        // Binary search for LCA
        for (int j = LOG - 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) {
        return depth[u] + depth[v] - 2 * depth[query(u, v)];
    }
};

วิธีที่ 2: Euler Tour + RMQ (Sparse Table)

Preprocess ใน $O(n \log n)$ , Query ใน $O(1)$

แนวคิด

ทำ Euler Tour บน tree
LCA(u, v) = node ที่มี depth น้อยที่สุดระหว่าง first occurrence ของ u และ v

Implementation

class LCA_RMQ {
    int n, LOG;
    vector<vector<int>> adj;
    vector<int> euler, first, depth;
    vector<vector<int>> sparse;  // sparse[i][j] = index with min depth in euler[i..i+2^j-1]
    
    void dfs(int u, int p, int d) {
        first[u] = euler.size();
        euler.push_back(u);
        depth[u] = d;
        
        for (int v : adj[u]) {
            if (v != p) {
                dfs(v, u, d + 1);
                euler.push_back(u);  // Add u again when returning
            }
        }
    }
    
    void buildSparse() {
        int m = euler.size();
        LOG = 32 - __builtin_clz(m);
        sparse.assign(m, vector<int>(LOG));
        
        // Initialize for length 1
        for (int i = 0; i < m; i++) {
            sparse[i][0] = i;
        }
        
        // Build sparse table
        for (int j = 1; j < LOG; j++) {
            for (int i = 0; i + (1 << j) <= m; i++) {
                int left = sparse[i][j-1];
                int right = sparse[i + (1 << (j-1))][j-1];
                sparse[i][j] = (depth[euler[left]] < depth[euler[right]]) ? left : right;
            }
        }
    }
    
public:
    LCA_RMQ(int n) : n(n), adj(n), first(n), depth(n) {}
    
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    void build(int root = 0) {
        euler.clear();
        dfs(root, -1, 0);
        buildSparse();
    }
    
    int query(int u, int v) {
        int l = first[u], r = first[v];
        if (l > r) swap(l, r);
        
        int len = r - l + 1;
        int k = 31 - __builtin_clz(len);
        
        int left = sparse[l][k];
        int right = sparse[r - (1 << k) + 1][k];
        
        return (depth[euler[left]] < depth[euler[right]]) ? euler[left] : euler[right];
    }
    
    int distance(int u, int v) {
        return depth[u] + depth[v] - 2 * depth[query(u, v)];
    }
};

วิธีที่ 3: Tarjan’s Offline LCA

สำหรับ offline queries - ตอบ queries ทั้งหมดพร้อมกัน

Time: $O((n + q) \cdot \alpha(n))$ โดยที่ $\alpha$ คือ inverse Ackermann

class TarjanLCA {
    int n;
    vector<vector<int>> adj;
    vector<vector<pair<int, int>>> queries;  // queries[u] = {(v, query_index)}
    vector<int> parent, rank_, ancestor;
    vector<bool> visited;
    vector<int> answer;
    
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return;
        if (rank_[x] < rank_[y]) swap(x, y);
        parent[y] = x;
        if (rank_[x] == rank_[y]) rank_[x]++;
    }
    
    void dfs(int u, int p) {
        ancestor[find(u)] = u;
        
        for (int v : adj[u]) {
            if (v != p) {
                dfs(v, u);
                unite(u, v);
                ancestor[find(u)] = u;
            }
        }
        
        visited[u] = true;
        
        for (auto& [v, idx] : queries[u]) {
            if (visited[v]) {
                answer[idx] = ancestor[find(v)];
            }
        }
    }
    
public:
    TarjanLCA(int n, int q) : n(n), adj(n), queries(n), 
        parent(n), rank_(n, 0), ancestor(n), visited(n, false), answer(q) {
        iota(parent.begin(), parent.end(), 0);
    }
    
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    void addQuery(int u, int v, int idx) {
        queries[u].push_back({v, idx});
        queries[v].push_back({u, idx});
    }
    
    vector<int> solve(int root = 0) {
        dfs(root, -1);
        return answer;
    }
};

ประยุกต์ใช้งาน

1. Distance between nodes

int dist(int u, int v) {
    return depth[u] + depth[v] - 2 * depth[lca(u, v)];
}

2. Path queries (Sum on path)

// Precompute: sum from root to each node
vector<long long> pathSum;

long long queryPath(int u, int v) {
    int l = lca(u, v);
    return pathSum[u] + pathSum[v] - 2 * pathSum[l] + value[l];
}

3. Check if node x is on path from u to v

bool onPath(int u, int v, int x) {
    int l = lca(u, v);
    return (lca(u, x) == x || lca(v, x) == x) && lca(l, x) == l;
}

4. Find meeting point of three nodes

int meetingPoint(int a, int b, int c) {
    int lab = lca(a, b);
    int lac = lca(a, c);
    int lbc = lca(b, c);
    
    // One of these is the meeting point
    return lab ^ lac ^ lbc;  // XOR gives the unique one
}

Complexity Comparison

Method	Preprocess	Query	Space
Binary Lifting	$O(n \log n)$	$O(\log n)$	$O(n \log n)$
Euler Tour + RMQ	$O(n \log n)$	$O(1)$	$O(n \log n)$
Tarjan (Offline)	$O((n+q) \alpha(n))$	-	$O(n + q)$

Tips

Binary Lifting ง่ายต่อการ implement และยืดหยุ่น
Euler Tour + RMQ เร็วที่สุดสำหรับ online queries
Tarjan ดีสำหรับ offline queries จำนวนมาก
LCA กับ Weighted Tree - เก็บ weighted sum ใน binary lifting table