树上倍增

第2题     [模板] LCA 查看测评数据信息

模板题：求 LCA（最近公共祖先）。

以 1 号节点为树的根。


输入格式

第一行两个正整数 n, m，表示树的节点数和询问的个数。

接下来 n - 1 行，每行两个正整数 u, v，表示树上有一条连接节点 u 和 v 的边。

接下来 m 行，每行两个正整数 u, v，表示询问节点 u 和 v 的最近公共祖先。


对于 40% 的数据，满足 1 ≤ n, m ≤ 100。

对于 60% 的数据，满足 1 ≤ n, m ≤ 104，数据随机生成。

对于 100% 的数据，满足 1 ≤ n, m ≤ 105。


输出格式

输出共 m 行，每行一个整数表示答案。

输入/输出例子1

输入：

5 2

1 2

1 3

2 4

2 5

1 4

5 4


输出：

1

2

样例解释

无

解释1：https://www.luogu.com.cn/problem/solution/P3379 （第一篇题解详细解释，按深度做）

解释2：按时间戳做

#include <bits/stdc++.h>
using namespace std;

const int N=1e5+5, M=32;
int n, m, u1, v1, vis[N], f[N][M], cnt=0;
//vis[i]:节点i访问时间
//f[i][j]:从节点f，走2^j步，能到的点
vector<int> a[N];
void dfs(int u, int fa) //u:当前节点  fa:他的父亲节点
{
	vis[u]=++cnt; //访问时间
	f[u][0]=fa; //u点走1步到父亲
	for (int i=1; i<=20; i++) //2^20就行，看题目范围
		f[u][i]=f[f[u][i-1]][i-1]; //拆两半，u节点跳2^i步=u节点跳2^(i-1)步+u节点跳2^(i-1)步=f [  f[u][i-1]  ] [i-1]
	//意思是u的2^i祖先等于u的2^(i-1)祖先的2^(i-1)祖先
　　//2^i = 2^(i-1) + 2^(i-1)
	for (int i=0; i<a[u].size(); i++)
	{
		int v=a[u][i];
		if (v!=fa) dfs(v, u); 
	}
}
int lca(int u, int v)
{
	if (vis[u]>vis[v]) swap(u, v); //保证v访问时间是大的
	if (u==v) return u; //别忘了加
	
	for (int i=20; i>=0; i--)//从后往前推。原因如下
//从小向大跳，5≠1+2+4,所以我们还要回溯一步，然后才能得出5=1+4；而从大向小跳，直接可以得出5=4+1。这也可以拿二进制为例，5(101)，从高位向低位填很简单，如果填了这位之后比原数大了，那我就不填，这个过程是很好操作的。
		if (vis[f[v][i]]>vis[u])  //见下 解释1
			v=f[v][i];
	
	return f[v][0]; //距离u，v最近公共祖先还差一步
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i=1; i<n; i++)
	{
		scanf("%d%d", &u1, &v1);
		a[u1].push_back(v1);
		a[v1].push_back(u1);
	}
	dfs(1, 1); //这里定1号节点的父亲节点是自己
	
	while (m--)
	{
		scanf("%d%d", &u1, &v1);
		printf("%d\n", lca(u1, v1));
	}
	return 0;
}

 解释1

 例如这张图，u，v最近公共祖先是三角型那里

有一些二分的思想（v点时间必须>u点时间，且>三角型点时间）

v点先尝试跳64步，发现不行，跳32步.....一直到跳16步，才可以比三角形大，也比u大（因为先跟遍历，所以那个点时间必然>u时间）

发现可行就抬高，然后最终就一定会在三角形点的下面一个点