最近公共祖先（lca）_alaso_shuang的博客-爱代码爱编程

//最近公共祖先
//暴力做法 
//向上标记法和同步前进法 
int LCA(int u,int v)
{
	if(u == v)return u;
	flag[u] = 1;
	while(fa[u] != u)//u向上走到根 
	{
		u = fa[u];
		flag[u] = 1;
	}
	if(flag[v])return v;
	while(fa[v] != v)
	{
		v = fa[v];
		if(flag[v])return v;
	}
	return 0;
 } 
 //树上倍增
 //方法：创建ST表，利用ST表求解LCA
 //f(i,j) = f(f(i,j-1),j-1); 
 
void ST_create()
{
 	for(int j = 1;j <= k;j++)
 	for(int i = 1;i <= n;i++)//表示i先走2 ^ (j-1)步到达f[i][j-1]，再走2 ^ (j-1)步 
 	f[i][j] = f[f[i][j-1]][j-1];
}

int LCA_ST_query(int x,int y)
{
	if(d[x] > d[y]) swap(d[x],d[y]);// 保证x的深度小于等于y 
	for(int i = k;i >= 0;i--) if(d[f[y][i]] >= d[x]) y = f[y][i];//y向上走到与x同一深度 
	
	if(x == y) return x;
	for(int i = k;i >= 0;i--) 
	if(f[x][i] != f[y][i]) x = f[x][i],y = f[y][i];
	return f[x][0];//返回x的父亲 
}