用倍增法求LCA,板子好打,不容易错。
//fa[x][i] 表示从结点x向上跳2^i的结点,dp[x][0]表示x的父节点
void dfs(int x)
{
vis[x]=1;
for(int i=1;i<=18;i++) //预处理
{
if(deep[x]<(1<<i)) break;
fa[x][i]=fa[fa[x][i-1]][i-1];
}
for(int i=head[x];i;i=edge[i].next)
{
if(vis[edge[i].to]) continue;
fa[edge[i].to][0]=x;
deep[edge[i].to]=deep[x]+1;
dfs(edge[i].to);
}
}
int lca(int x,int y)
{
if(deep[x]<deep[y]) swap(x,y); //使得x为深度大的
int d=deep[x]-deep[y]; //求深度差
for(int i=0;i<=18;i++)
if(d&(1<<i)) x=fa[x][i]; //使得x的深度与y的相同
if(x==y) return x; //若x与y已经相等,则说明y是x的祖先,返回x.
for(int i=18;i>=0;i--)
if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i]; //同时向上"跳";
return fa[x][0];
}