树上倍增

FJ_00460 · 2025-01-05 19:07:33 · 算法·理论

树上倍增

豪用

求第Y个祖先

N个节点的树，M次询问第X个节点的第Y个祖先 n, m <= 1e4

定义数组F[x][y] = f[x][ 2 ^ y] 。

节点祖先的性质，易得F[x][y + 1] = F[F[x][y]][y]

从小到大枚举y，求出一切节点的F[x][y]，如此往复，通过已知的F[x][y]求出F[x][y + 1]。

y 的上界：O(long _ n)，因此预处理O(n * log_n)

模版

void init(){
    for(int i = 1 ; i <= n ; i ++)
        F[i][0] = fa[i];
    for(int i = 1 ; i <= 20; i ++)
        for(int j = 1 ; j <= n ; j ++){
            if(F[j][i - 1] > 0 && F[F[j][j - 1]][j - 1] > 0)
                F[j][i] = F[F[j][i - 1]][i - 1];
        }
}

int f(int x, int n){
    for(int i = 20; i >= 0;; i --){
        if(n >= (1 << i)){
            n -= (1 << i);
            x = F[x][i];
        }
    }
    return x;
}

求LCA

倍增求F[x][k]，代表节点x的第 2^k 个祖先。