求解倍增求LCA的常数优化

int lca(int x,int y){
    if(dep[x]<dep[y]) swap(x,y);
    while(dep[x]>dep[y]){
        x=fa[x][lg[dep[x]-dep[y]]-1];//lg数组是log2()
    }
    if(x==y) return x;
    for(int i=lg[dep[x]]-1;i>=0;i--){
        if(fa[x][i]!=fa[y][i]){
            x=fa[x][i];y=fa[y][i];
        }
    }
    return fa[x][0];
}

for(int i=1;i<=n;i++)
    	lg[i]=lg[i-1]+(1<<lg[i-1]==i);