倍增求LCA

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
namespace MultipLCA
{
    vector<int> G[MAX];
    int fa[MAX][20],dep[MAX];

    void dfs(int now,int father)
    {
        dep[now]=dep[father]+1,fa[now][0]=father;
        for(int i=1;i<=__lg(dep[now]);++i) fa[now][i]=fa[fa[now][i-1]][i-1];
        for(auto to:G[now]) if(to!=father) dfs(to,now);
    }
    inline int LCA(int x,int y)
    {
        if(dep[x]<dep[y]) Swp(x,y);
        while(dep[x]>dep[y]) x=fa[x][__lg(dep[x]-dep[y])];
        if(x==y) return x;
        for(int i=__lg(dep[x]);~i;--i) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
        return fa[x][0];
    }
}