dfs 序 LCA

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int n,m,rt,tot,cnt,dfn[500010],head[500010],to[1000010],nex[1000010];
inline void add(int x,int y){to[++cnt]=y,nex[cnt]=head[x],head[x]=cnt;}
int F[19][500010];
inline int get(int x,int y){return dfn[x]<dfn[y]?x:y;}
void dfs(int x,int fa)
{
    F[0][dfn[x]=++tot]=fa;
    for(int i=head[x];i;i=nex[i])if(to[i]!=fa)dfs(to[i],x);
}
inline int LCA(int x,int y)
{
    if(x==y)return x;
    if((x=dfn[x])>(y=dfn[y]))swap(x,y);
    int k=__lg(y-x++);
    return get(F[k][x],F[k][y-(1<<k)+1]);
}
inline void build()
{
    dfs(rt,0);
    for(int i=1;i<19;++i)
    {
        for(int j=1;j+(1<<i)-1<=n;++j)
        F[i][j]=get(F[i-1][j],F[i-1][j+(1<<(i-1))]);
    }
}