LCA [Binary Lifting]

int n, h, timer;
vector<vector<int>> edges, up;
vector<int> tin, tout;

void lca_dfs(int u, int p)
{
    tin[u] = ++timer;
    up[u][0] = p;
    for (int i = 1; i <= h; i++)
        up[u][i] = up[up[u][i - 1]][i - 1];
    for (int v : edges[u])
        if (v != p)
            lca_dfs(v, u);
    tout[u] = ++timer;
}

void preprocess(int root)
{
    timer = 0;
    for (h = 1; h < n; h *= 2);
    tin.resize(n, 0), tout.resize(n, 0);
    up.resize(n, vector<int>(h + 1, -1));
    lca_dfs(root, root);
}

bool is_ancestor(int u, int v)
{
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}

int lca(int u, int v)
{
    if (is_ancestor(u, v)) return u;
    if (is_ancestor(v, u)) return v;

    for (int i = h; i >= 0; i--)
        if (!is_ancestor(up[u][i], v))
            u = up[u][i];

    return up[u][0];
}