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

Материал из Олимпиадное программирование в УлГТУ
Перейти к: навигация, поиск
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];
}

Ссылки