dfs板子没有处理dep，需要的时候顺手加。

bfs

void bfs()//完成depth fa
{
    memset(depth,0x3f,sizeof depth);
    queue<int> q;
    depth[0]=0;//哨兵
    q.push(root);
    depth[root]=1;

    while(q.size())
    {
        int t=q.front();
        q.pop();
        for(auto to:g[t])
        {
            if(depth[to]>depth[t]+1)//注意是大于 xx加一
            {
                depth[to]=depth[t]+1;
                q.push(to);

                fa[to][0]=t;
                for(int k=1;k<=15;k++)
                {
                    fa[to][k]=fa[fa[to][k-1]][k-1];
                }
            }

        }
    }

}

int lca(int a,int b)
{
    if(depth[a]<depth[b]) swap(a,b);

    for(int k=15;k>=0;k--)
    {
        if(depth[fa[a][k]]>=depth[b])
            a=fa[a][k];
    }

    if(a==b) return a;

    for(int k=15;k>=0;k--)
    {
        if(fa[a][k]!=fa[b][k])
        {
            a=fa[a][k];
            b=fa[b][k];
        }
    }
    return fa[a][0];
}

dfs

void initlca(int x){
    for(int i=0;i<=20;i++) fa[x][i+1] = fa[fa[x][i]][i];
    for(auto y:g[x]){
        if(y==fa[x][0]) continue;
        fa[y][0] = x;
        initlca(y);
    }
}
int lca(int x,int y){
    if(dep[x]<dep[y]) swap(x,y);
    for(int d=dep[x]-dep[y],i=0;d;d>>=1,i++){
        if(d&1) x = fa[x][i];
    }
    if(x==y) return x;
    for(int i=20;i>=0;i--){
        if(fa[x][i]!=fa[y][i]) x  = fa[x][i],y = fa[y][i];
    }
    return fa[x][0];
}