Метод двоичного подъёма

void dfs(int v, int parent) { //если v - корень, то parent == v
    tIn[v] = timer++;
    p[v][0] = parent;
    for (int i = 1; i < MAX_H; i++)
        p[v][i] = p[p[v][i - 1]][i - 1];
    for (int i = 0; i < g[v].size(); i++)
        dfs(g[v][i], v);
    tOut[v] = timer++;
}

bool isAncestor(int a, int b) {
    return tIn[a] <= tIn[b] && tOut[b] <= tOut[a];
}

int lca(int a, int b) {
    if (isAncestor(a, b))
        return a;
    if (isAncestor(b, a))
        return b;
    for (int i = MAX_H - 1; i >= 0; i--) {
        if (!isAncestor(p[a][i], b))
            a = p[a][i];
    }
    return p[a][0];
}

Ссылки

• e-maxx.ru — Наименьший общий предок. Нахождение за O(log N) (метод двоичного подъёма)
• neerc.ifmo.ru/wiki — Метод двоичного подъёма
• CodeLibrary — LCA: Sparse Table (несмотря на название, приведён код метода двоичного подъёма)
• Algos — Finding LCA (Least common ancestor) of two vertices in the tree