【模板】LCA的倍增算法

在线算法

和st表求区间最值类似
暴力求区间最值需要一个一个比较
暴力求lca需要一步一步爬树
st表用倍增比较一段和一段间的最值
启发我们求lca也用倍增，一次向上爬$2^i$2i个点

设$f(i,j)$f(i,j)表示点i向上跳$2^j$2j步之后的点
边界：$f(i,0)=fa[i]$f(i,0)=fa[i] （表示向上跳一步的点）
转移：跳$2^j$2j步，先跳$2^{j-1}$2j−1步，再跳$2^{j-1}$2j−1步
$f(i,j)=f(f(i,j-1),j-1)$f(i,j)=f(f(i,j−1),j−1)

先调整u,v到同一深度（深的点向上爬）
不过别一步一步爬，用f数组向上跳
再让u,v一起向上跳
从大到小枚举j，试图让u和v向上跳2^j步，如果u和v将要跳到同一个点，就不跳（因为可能跳到lca的上面），否则就爬树
最后向上爬一步就是lca，时间复杂度O(logn)

这张图看起来好像到处都是 我也贴一下吧

例题&板子 传送门：poj 1986

#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
#define MAXN 50005
struct node{
	int v,w;
};
int n,m;
vector<node>G[MAXN];
int dis[MAXN],dep[MAXN],f[MAXN][20];
//f[i][j]:点i向上跳2^j步之后的点
void Init()
{
	for(int j=1;(1<<j)<=n;j++)//内外层的顺序主要是因为更新时j是由小到大来的，而i(f[i][j-1])相对不确定 
		for(int i=1;i<=n;i++)//而如果用j为外层 那么也是可以保证i(f[i][j-1])已经被更新 
			if(f[i][j-1]!=-1)
				f[i][j]=f[f[i][j-1]][j-1]; 
	return ;
}
void swp(int &a,int &b)
{
	int t=a;
	a=b;
	b=t;
	return ;
}
void dfs(int u,int p,int d)
{
	dep[u]=d;
	for(int i=0;i<G[u].size();i++)
	{
		int v=G[u][i].v,w=G[u][i].w;
		if(v==p) continue;
		f[v][0]=u;
		dis[v]=dis[u]+w;
		dfs(v,u,d+1);
	}
}
int LCA(int u,int v)
{
	if(dep[u]<dep[v])
		swp(u,v);//u的深度更深
	int k=0;
	while((1<<k)<=dep[u])//j的范围
		k++;
	k--;
	//较深的那一个点爬到与另一个点相等的深度
	for(int j=k;j>=0;j--)
		if(dep[u]-(1<<j)>=dep[v])
			u=f[u][j];
	while(dep[u]>dep[v])
		u=f[u][0];
	if(u==v) return u;
	for(int j=k;j>=0;j--)
	{
		if(f[u][j]!=f[v][j]&&f[u][j]!=-1&&f[v][j]!=-1)
			u=f[u][j],v=f[v][j];
	}
	return f[u][0];
}
int ans(int u,int v)
{
	return dis[u]+dis[v]-2*dis[LCA(u,v)];
}
int main()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		scanf("%d %d %d %*s",&u,&v,&w);
		node t;t.v=v,t.w=w;
		G[u].push_back(t);
		t.v=u,G[v].push_back(t);
	}
	memset(f,-1,sizeof(f));//-1的状态即为不合法的状态(比方说，跳出去了
	dfs(1,-1,0);
	Init();//倍增 处理f函数 
	int T;
	scanf("%d",&T);
	while(T--)
	{
		int u,v;
		scanf("%d %d",&u,&v);
		printf("%d\n",ans(u,v));
	}
	return 0;
}

然后就是 倍增的思想可以解决一些树上路径问题，而之前的RMQ的方法却不能解决