LCA offline#5217

LCA offline (Розбір)

Solution

General Idea : We are given a sequence of operations on a tree that initially contains only the root node $1$ . There are two types of queries:

ADD a b: Attach node $b$ as a child of node $a$ .
GET a b: Output the Lowest Common Ancestor (LCA) of nodes $a$ and $b$ .

Since the tree is built dynamically, we first store all ADD operations to construct the final tree. After building the tree, we preprocess it using Binary Lifting to answer each LCA query in $O (lo g n)$ \mathcal{O}(\log n).

—

Binary Lifting Preprocessing

For every node $v$ , we precompute: [ anc[v][i] = the 2^i-th ancestor of node v ] along with its depth.

This allows us to:

Lift a node up by any number of levels in $lo g n$
Compute LCA in $lo g n$ time

—

LCA Computation

To find $LCA (u, v)$ \text{LCA}(u, v):

If depths are different, lift the deeper node.
If $u = v$ u = v, it is the LCA.
Otherwise, lift both nodes together from the highest possible jump.
The parent of either node is the LCA.

—

Time Complexity

Building the tree: $O (n)$
Preprocessing Binary Lifting: $O (n lo g n)$ \mathcal{O}(n \log n)
Each GET query: $O (lo g n)$ \mathcal{O}(\log n)

—

#include <bits/stdc++.h>
using namespace std;

class LCA {
public:
    int N, LOG;
    vector<vector<int>> adj, parent;
    vector<int> depth;

    LCA(int n, vector<vector<int>>& g, int root = 1) {
        N = n;
        adj = g;
        LOG = 0;
        while ((1 << LOG) <= N) LOG++;
        parent.assign(N + 1, vector<int>(LOG, 0));
        depth.assign(N + 1, 0);
        dfs(root, 0);
    }

    void dfs(int u, int p) {
        parent[u][0] = p;
        for (int i = 1; i < LOG; i++)
            parent[u][i] = parent[parent[u][i - 1]][i - 1];

        for (int v : adj[u]) {
            if (v == p) continue;
            depth[v] = depth[u] + 1;
            dfs(v, u);
        }
    }

    int lift(int u, int k) {
        for (int i = 0; i < LOG; i++)
            if (k & (1 << i))
                u = parent[u][i];
        return u;
    }

    int get_lca(int u, int v) {
        if (depth[u] < depth[v]) swap(u, v);
        u = lift(u, depth[u] - depth[v]);
        if (u == v) return u;

        for (int i = LOG - 1; i >= 0; i--) {
            if (parent[u][i] != parent[v][i]) {
                u = parent[u][i];
                v = parent[v][i];
            }
        }
        return parent[u][0];
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int q;
    cin >> q;

    vector<vector<int>> adj(500000 + 5);
    vector<pair<int,int>> queries;

    for (int i = 0; i < q; i++) {
        string s;
        int a, b;
        cin >> s >> a >> b;
        if (s == "ADD") {
            adj[a].push_back(b);
            adj[b].push_back(a);
        } else {
            queries.push_back({a, b});
        }
    }

    LCA lca(500000, adj);

    for (auto &it : queries) {
        cout << lca.get_lca(it.first, it.second) << "\n";
    }

    return 0;
}