倍增LCA

引子

什么？你还不知道什么是LCA？LCA就是树上两个节点的最近公共祖先。
所以，对于怎么找LCA，是个人都会想到一个办法，让两个节点不断向上移动，只要重合了就是LCA了，嘿嘿嘿
然鹅，一个一个移动太慢，只要数据过了 $10^8$ 分分钟 T 飞~
所以，我们需要一个快速的移动方式，比如，成几何级数的移动，这就是倍增算法

基本思路

既然要成几何级数的移动速度，要找个底数，比如2吧，每次移动 $2^k$ 个
要想一次移动这么多，肯定要预处理，不如先预处理一个数组 $grand[i][j]$ 表示 $i$ 向上跳 $2^k$ 个是谁，跳出这棵树的值就为-1吧
怎么判断已经跳到了LCA呢？毕竟公共祖先不只有LCA一个
不如就不直接跳到LCA，把所有跳到相同节点的情况都视为跳出树了，一直跳直到跳不动了为止，这时候两个节点的父节点就是LCA了，是不是特别机智~

预处理

怎么预处理出 $grand$ 数组呢？什么？你想一个个往上跳，然后取对数？省省吧，有这功夫早就 T 飞了，我们需要一个更高效的方法，最好能利用已经求出的 $grand$ 数组
那不就是动态规划嘛，让我们来凑一手状态转移方程
首先， $i$ 向上跳 $2^k$ 个可以分解成两个动作，先向上跳 $2^{k-1}$ 个，再向上跳 $2^{k-1}$ 个
$i$ 向上跳 $2^{k-1}$ 个不就是 $grand[i][k-1]$ 嘛，套个娃，再向上跳 $2^{k-1}$ 个当然就是 $grand[grand[i][k-1]][k-1]$ 。于是我们得出方程：

grand[i][k]=grand[grand[i][k-1]][k-1]

瞅瞅这个方程，我们该用什么算法呢？
要想转移状态，必须要先求出 $grand[i][k-1]$ ，这告诉我们应该：

cpp
for(int k=;k< MAXON;k++)
{
  //求grand
}

再看，我们还要先求出 $i$ 的祖先节点的 $grand$ ，因为我们要用到 $grand[grand[i][k-1]][k-1]$ 嘛，这好说，来一手 $dfs$ 深度优先搜索就好了，顺便还可以记录每个节点的父节点和深度，一举两得
于是我们竟然可以写出代码了先用邻接表存图：

cpp
	struct edge
	{
		int to;//这条边到达的点
		int next;//下一条边
	}Edge[MAXON];
	int head[MAXON];//head[i]表示由i开始的第一条边的编号
	int tot=0;//总边数
	int grand[500010][30];
	int fa[MAXON];
	void add_dege(int from, int to)
	{
		tot++;//当前边的编号
		Edge[tot].to = to;
		if (from != -1)
			Edge[tot].next = head[from];//插入在前
		head[from] = tot;//由于这条边插入在了前面,故当前边就是由from开始的第一条边
	}

cpp
void dfs(int from, int now)
	{
		fa[now] = from;//记录父节点
		int start = head[now];//从第一个子节点开始找
		if (from != -1)//若不是根节点,深度为父节点深度+1(根节点为0)
			dep[now] = dep[from] + 1;
		//int g = log2(dep[now]) ;
		int g = lg[dep[now]];
		if (from != -1)//根节点没有父节点
			grand[now][0] = from;//2^0=1,即父节点
		for (int i = 1; i < = g; i++)
		{
			grand[now][i] = grand[grand[now][i - 1]][i - 1];//状态转移方程
		}
		while (start)//一个一个找孩子
		{
			if (Edge[start].to == from)//若相连节点不是父节点
			{
				start = Edge[start].next;
				continue;
			}
			dfs(now, Edge[start].to);//继续搜索子节点
			start = Edge[start].next;//搜索下一个子节点
		}
	}

跳！

预处理好了，接下来就是跳了
怎么跳呢？先跳到同一高度，然后什么都好说

cpp
		if (dep[a] > dep[b])//统一b深度大于a
		{
			a = a + b;//a此时等于原来的a,b之和
			b = a - b;//b此时等于原来的a
			a = a - b;//a此时等于原来的b
		}//神奇的交换方法
		int deep = dep[b] - dep[a];//深度差
		//int step = log2(deep);
		int step = lg[deep];//最大要走的步数
		for (int i = step; i >= 0; i--)//先让b跳到和a同一深度
		{
			if (dep[grand[b][i]] < dep[a]) continue;//跳过头了,不跳
			else
			{
				b = grand[b][i];//没跳过头,跳
			}
		}
		if (a == b) return a;//若相等,则已经找到LCA

这里为什么要有个step呢，因为先封个顶，一点点下降，能跳再跳，万一就跳出去了呢
然后就是两个节点一起向上跳了

cpp
		step = lg[dep[a]]; //要走的步数
		//step = log2(dep[a]);
		for (int i = step; i >= 0; i--)
		{
			if (grand[a][i] == grand[b][i]) continue;//跳过头了,不跳
			else//没跳过头,跳
			{
				a = grand[a][i];
				b = grand[b][i];
			}
		}
		return fa[a];//最后他们的父节点就是LC

要问这个 $lg$ 数组是怎么来的？洛谷上抄的，嘿嘿嘿

cpp
	for (int i = 1; i < = n; i++) //常数优化,预先算出log_2(i)+1的值，用的时候直接调用就可以了
		lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);  //看不懂的可以手推一下

完整代码

我写这玩意的时候特别喜欢class，于是。。。码风奇丑，凑合着看吧。。。

cpp
#include<cmath>
#include<cstdio>
#include<iostream>
using namespace std;
const int MAXON = 1000010;
int dep[MAXON];//dep[i]代表编号为i的点所处的深度
int lg[MAXON];
class Graph
{
private:
	struct edge
	{
		int to;//这条边到达的点
		int next;//下一条边
	}Edge[MAXON];
	int head[MAXON];//head[i]表示由i开始的第一条边的编号
	int tot;//总边数
	int grand[500010][30];
	int fa[MAXON];
public:
	Graph()
	{
		tot = 0;
	}
	void add_dege(int from, int to)
	{
		tot++;//当前边的编号
		Edge[tot].to = to;
		if (from != -1)
			Edge[tot].next = head[from];//插入在前
		head[from] = tot;//由于这条边插入在了前面,故当前边就是由from开始的第一条边
	}
	void dfs(int from, int now)
	{
		fa[now] = from;//记录父节点
		int start = head[now];//从第一个子节点开始找
		if (from != -1)//若不是根节点,深度为父节点深度+1(根节点为0)
			dep[now] = dep[from] + 1;
		//int g = log2(dep[now]) ;
		int g = lg[dep[now]];
		if (from != -1)//根节点没有父节点
			grand[now][0] = from;//2^0=1,即父节点
		for (int i = 1; i <= g; i++)
		{
			grand[now][i] = grand[grand[now][i - 1]][i - 1];//状态转移方程
		}
		while (start)//一个一个找孩子
		{
			if (Edge[start].to == from)//若相连节点不是父节点
			{
				start = Edge[start].next;
				continue;
			}
			dfs(now, Edge[start].to);//继续搜索子节点
			start = Edge[start].next;//搜索下一个子节点
		}
	}
	int lca(int a, int b)
	{
		if (dep[a] > dep[b])//统一b深度大于a
		{
			a = a + b;//a此时等于原来的a,b之和
			b = a - b;//b此时等于原来的a
			a = a - b;//a此时等于原来的b
		}//神奇的交换方法
		int deep = dep[b] - dep[a];//深度差
		//int step = log2(deep);
		int step = lg[deep];//最大要走的步数
		for (int i = step; i >= 0; i--)//先让b跳到和a同一深度
		{
			if (dep[grand[b][i]] < dep[a]) continue;//跳过头了,不跳
			else
			{
				b = grand[b][i];//没跳过头,跳
			}
		}
		if (a == b) return a;//若相等,则已经找到LCA
		step = lg[dep[a]]; //要走的步数
		//step = log2(dep[a]);
		for (int i = step; i >= 0; i--)
		{
			if (grand[a][i] == grand[b][i]) continue;//跳过头了,不跳
			else//没跳过头,跳
			{
				a = grand[a][i];
				b = grand[b][i];
			}
		}
		return fa[a];//最后他们的父节点就是LCA
	}
};
Graph G;
int main()
{
	int n, m, s;
	//cin >> n >> m >> s;
	scanf("%d%d%d", &n, &m, &s);
	for (int i = 1; i <= n; i++) //常熟优化,预先算出log_2(i)+1的值，用的时候直接调用就可以了
		lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);  //看不懂的可以手推一下
	n--;
	while (n--)
	{
		int a, b;
		//cin >> a >> b;
		scanf("%d%d", &a, &b);
		G.add_dege(a, b);
		G.add_dege(b, a);
	}
	G.dfs(-1, s);
	while (m--)
	{
		int a, b;
		//cin >> a >> b;
		scanf("%d%d", &a, &b);
		int ans = G.lca(a, b);
		if (ans == -1)
			printf("%d\n", s);
		//cout << s << endl;
		else
			printf("%d\n", ans);
		//cout << ans << endl;
	}
	return 0;
}

目录

倍增LCA

引子

基本思路

预处理

跳！

完整代码