题目描述

给定一棵 $n$ 个结点的树（结点标号 $1$~$n$ ）以及树中结点的边，结点 s 为树的根。

有 $m$ 次询问，请求出每次询问的两个结点 $x$ 和 $y$ 的最近的公共祖先结点。

输入格式

第 $1$ 行输入 $3$ 个整数 $n$、$m$、$s$（$n \le 500000$，$m \le 500000$，$1 \le s \le n$）；

接下来 $n−1$ 行，每行两个整数 $a$ 和 $b$ ，结点 $a$ 和 $b$ 是父子关系，但不保证 $a$ 是 $b$ 的父，数据保证一定能构成树；

接下来 $m$ 行，每行两个整数 $x$，$y$，表示要求出 $x$ 和 $y$ 结点的公共祖先。

输出格式

输出 $m$ 行，每行一个整数，表示 $m$ 次询问求出的结果。

样例

5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5

4
4
1
4
4

算法分析

这条题还是求树上两个节点的最近公共祖先 (LCA)，学习本题之前，应该先学习往上标记法求 LCA。本题因为树的顶点数更多，询问次数更多，所以如果还是使用往上标记法就会超时，我们要学习新的方法：倍增法，但是倍增法是往上标记法的增强算法，所以首先应该要吃透往上标记法。

往上标记法其实是把顶点从下网上看，看成一条链，每次往上走一步的去遍历这条链。经过顶点 x 和经过顶点 y 的两条链的交汇处就是他们的最近公共祖先。在向上遍历和打标记的是时候，因为一次跳转一层，效率比较低。

改进的思想是，我们用一个数组来记录从任意一个节点往上走 $2^j$ 步之后的祖先。$2^0=1$，$2^1=2$，$2^2=4$，$2^3=8$，$2^4=16$，$2^5=32$，$2^6=64$......，假设 x 顶点要往上走 55 步，其实就是跳转 55=32+16+4+2+1= $2^5+2^4+2^2+2^1+2^0$，也就是说：

1. 从 x 顶点往上先跳 1 次跳到距离它 32 层的祖先 $x_2$ （这个跳转要一步完成）；

2. 然后从 $x_2$ 往上跳到距离它 16 层的那个祖先 $x_3$（这个跳转也要一步完成）；

3. 再从 $x_3$ 往上跳到距离它 4 层的那个祖先 $x_4$（这个跳转也要一步完成）；

4. 再从 $x_4$ 往上跳到距离它 2 层的那个祖先 $x_5$（这个跳转也要一步完成）；

5. 再从 $x_5$ 往上跳到距离它 1 层的那个祖先 $x_6$（这个跳转也要一步完成）；

所以，一共是跳转了 5 次，就从 x 跳到了距离它 55 层的一个祖先，大幅度提升了跳转的效率。

有了上述的这个思想，我们介绍一下倍增法求最近公共祖先的算法步骤

1. 根据最大的深度来设定倍增法跳转数组，如果有 n 个顶点，最大深度为 n (根节点的深度为 1，极端情况下，除了最后一个顶点之外其余顶点都只有 1 个儿子，这样得到的最大深度最大)。$2^{max} \ge n$ ，所以也相当于是 $max \ge \ln n$

2. fa 是二维数组，第一个下标代表顶点编号；第二个下标 j 是改顶点向上跳转 $2^j$ 层，数组存放的内容为跳转之后的顶点编号。例如 fa[997][0] 的意思是顶点 997 的父亲的编号；fa[997][1] 是 997 的爷爷的编号，fa[997][2] 表示的是 997 爷爷的爷爷的编号；fa[997][5] 表示顶点 997 往上跳 $2^5$ = 32 层的对应祖先的编号

3. 构建树的时候，要把上述的 fa 数组算好。公式是 fa[p][0] = father; fa[p][j] = fa[fa[p][j-1]][j-1] ，意思是从 p 开始，先往上跳 $2^j$ 层分两步完成，先从 p 开始跳 $2^{j-1}$ 层，然后再从这个位置往上跳跳 $2^{j-1}$ 层)

4. 求顶点 x 和 y 的公共祖先，分成几个小步骤。

   • 第一个小步骤是统一 x 和 y 的深度，假设 x 的深度更深，则让 x 往上跳，跳到和 y 同样深度（基于上面算好的 fa 二维数组来跳）；
   • 统一深度之后，x 和 y 是同一个顶点，那么就说明最初的 x 和 y 是直系亲属，就只找到了 LCA 了；
   • 否则，x 和 y 往上找。因此这个时候 x 和 y 是处于同一深度，他们往上找的时候也是同步往上找，比较的也是同一深度的祖先。跳转的时候其实是让 x 和 y 往上跳 $2^j$ 层，j 从大到小枚举，如果 x 的 $2^j$ 层祖先等于 y 的 $2^j$ 层祖先，就说明过了（跳多了），所以就不能跳，否则就同步往上跳。
   • 退出循环的时候，x 或者 y 的父亲就是他们的 LCA。

完善程序

#include<bits/stdc++.h>
using namespace std;
struct Edge
{
	int v,next;
}e[1000001];
int h[500001],depth[500001],fa[500001][23]; // h 数组存放顶点的边链头
int n,m,s,tot;
void add_edge(int From, int To)
{
	e[填空(1)].v=To;
	e[tot].next = 填空(2);
	填空(2) = tot;
}
void dfs(int p,int father)
{
	depth[p] = 填空(3);
	fa[p][0] = 填空(4);

	for(int i=1;i<=22;i++)
		fa[p][i] = 填空(5);  // 这个地方是整个算法和关键，2^i = 2^(i-1) * 2^(i-1)，为了条 2^j 层，相当于跳了两次 2^(j-1) 层

	for(int i=h[p];i;i=e[i].next) // 递归调用，根据儿子去构建树
		if(填空(6))
			填空(7);

}
int LCA(int x,int y)
{
	if(depth[x]<depth[y]) swap(x,y);//交换x和y的值,确保 x 顶点的深度更深 

	for(int i=22;i>=0; i--)//二进制优化，必须从大王小枚举
	{
		if(填空(8))
			x=fa[x][i];
		
		if(x==y) return x;
	}

	//来到这里，x 和 y 是处于同一深度的
	for(int i=22; i>=0; i--)//和二进制优化一个道理 
	{
		if(填空(9)) // 只要 x 和 y 的 2^j 祖先不是同一个人，就同步往上跳
		{
			x=fa[x][i];
			y=fa[y][i];
		}
	}

	//离开循环的时候，x 和 y 还是不相等的 2 个顶点，但是他们的父亲就一定是相同的
	return 填空(10);
}
int main()
{
	
	scanf("%d%d%d",&n,&m,&s);
	int x,y;
	for(int i=1;i<n;i++)
	{		
		scanf("%d%d",&x,&y);
		add_edge(x,y);
		add_edge(y,x);
	}

	dfs(s,0); // 构建树 

	while(m--)
	{
		scanf("%d%d",&x,&y);
		printf("%d\n",LCA(x,y));
	}
	return 0;
}

填空(1)：{{ input(1) }}

填空(2)：{{ input(2) }}

填空(3)：{{ input(3) }}

填空(4)：{{ input(4) }}

填空(5)：{{ input(5) }}

填空(6)：{{ input(6) }}

填空(7)：{{ input(7) }}

填空(8)：{{ input(8) }}

填空(9)：{{ input(9) }}

填空(10)：{{ input(10) }}