在线LCA模板

在线LCA

如求A，B两点的LCA，先计算出各个结点的深度d[]，然后，通过递推公式求出各个结点的2次方倍的祖先p[]，假设d[A] > d[B]，则找到d[p[A][i]] == d[B]也就是A的某一祖先与B深度相同，然后，u = p[A][i]，通过p[u][i] 与p[B][i]比较找出LCA(巧妙的利用二进制).

(p[a][b] 表示与a的距离为2^b的祖先，则p[a][0]表示为a的父亲。如 a->b->c->d->e，a为根， 则p[e][2] 为a)

递推公式：p[a][b] = p[p[a][b - 1]][b - 1]

/* 
2^17=131072; 
2^18=262144; 
*/  
const int POW = 18;  
void dfs(int u,int fa){  
    d[u]=d[fa]+1;  
    p[u][0]=fa;  
    for(int i=1;i<POW;i++) p[u][i]=p[p[u][i-1]][i-1];  
    int sz=edge[u].size();  
    for(int i=0;i<sz;i++){  
        int v=edge[u][i];  
        if(v==fa) continue;  
        dfs(v,u);  
    }  
}  
int lca( int a, int b ){  
    if( d[a] > d[b] ) a ^= b, b ^= a, a ^= b;  
    if( d[a] < d[b] ){  
        int del = d[b] - d[a];  
        for( int i = 0; i < POW; i++ ) if(del&(1<<i)) b=p[b][i];  
    }  
    if( a != b ){  
        for( int i = POW-1; i >= 0; i-- )   
            if( p[a][i] != p[b][i] )   
                 a = p[a][i] , b = p[b][i];  
        a = p[a][0], b = p[b][0];  
    }  
    return a;  
}