祖先

在一个有根树中，路过的点都被称为祖先，为了一般画我们把一个点本身也成为祖先，这样每个点都会有很多祖先，最近公共祖先就是，给我们两个点，离他们俩最近的一个公共祖先就是最近公共祖先，如图

如果两个点是重叠的，最近公共祖先就是它自己

求法

向上标记法（不常用）

从一个点开始，向根节点便利，遍历的过程当中，把他路过的所有的点标记一下 ，然后从另一个点做相同操作，当第一次走到被标记的的点的时候就是最近公共祖先，这个时间复杂度是O(n)的

倍增

先预处理一下每个点向上走$2^k$步的父亲是谁。
fa[i][j]表示从i开始，向上走$2^j$步所能走到的所有节点， 0 <= j <= logn(以2为底)

用递推的方式进行预处理

如图，也就是要求从i这个点开始，向上走$2^j$步，之后的点，接下来分成两种情况，第一种就是j=0，答案就是i的父节点，当j>0的时候，就分成两步，先跳到$2^{j-1}$,然后从这个点再往后跳$2^{j-1}$步，就跟图中一样

depth[]表示深度，规定根节点深度是1，然后根节点子节点的深度是2，再子节点深度是3，以此类推，就是到根节点的距离+1

这两个数组都可以用dfs 或者bfs来求

距离

求xy这两个点的公共祖先，分两步
1.先将两个点跳到同一层，其实就是让较深的那个点跳到跟较浅的那个点的同一层，这里就是把x跳到和y同一层

基于一个二进制拼凑的思想，比如已经预处理出来了2的k次方以内的数，想要凑出来t，就是看一下t的二进制表示，然后凑出来，就直接从小到大看，只要t大于2的当前位次方，就说明t是要包含这一个的，然后边减边比较

然后，应用到lca里面就是，x要跳到y，需要跳的就是depth[y] - depth[x]步，然后已经预处理出来了f[i][j]就从大到小枚举一下，凑出来这个数就好实际上不用凑出来这个数，只需要在枚举的时候，只要满足

这个条件就可以往上跳
2.让两个点同时往上跳（如果第一步进行完之后就是同一个点了的话，就可以直接结束，不用第二步了），一直到两个都是公共祖先的下一层为止，之所以不直接跳到公共祖先是为了方便判断

如果f[a][k] = f[b][k]的话，我们只能说f[a][k] 和f[b][k]是a和b的一个公共祖先，并不能说是最近公共祖先，但是如果f[a][k] != f[b][k]的话，就意味着f[a][k] = f[b][k]还没有走到公共祖先上，正因为这一点，才让跳到公共祖先的下一个点，就是如果相等的话，无法判断这个点是不是最近公共祖先，因为它还可能是最近公共祖先的上面的一个点，这无法判断

跳的时候也是按照二进制拼凑的思想，从大往小来枚举k，在枚举的过程当中，只要我们跳$2^K$步之后f[a][k] != f[b][k]，就说明他们还没有跳到应有的位置，就是还没有跳到最近公共祖先上，就可以让他们一起往上跳一次，直到k枚举完为止，枚举完之后x和y就算是走到了公共祖先的下一层，这时候，他们的公共祖先应该是从x或者y往上跳一步

这两步时间复杂度都是logn，预处理时间复杂度是nlogn的，这种倍增求lca的方式也是最常用的一种方式

在实际过程中，还会设置哨兵

基于RMQ的做法

首先把整棵树dfs遍历一遍，遍历的过程中记录一下dfs序列，这里记录的时候是每次遍历到，无论是回溯还是首次遍历都要记录一下，以下图为例

dfs序列应该是

这里还是找x和y之间距离，那就是一个8一个5，随便一个8一个5都可以，然后就转变成了区间最小值问题，就可以用RMQ或线段树来做

例题

祖孙询问

板子题不解释

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define fast ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
const int N = 40010;
vector<int> v[N];
int depth[N], fa[N][16];
queue<int> q;
int root, n, m;

void bfs()
{
	memset(depth, 0x3f, sizeof depth);
	depth[0] = 0; depth[root] = 1;
	q.push(root);
	while(q.size())
	{
		int t = q.front();
		q.pop();
		for(auto i : v[t])
		{
			if(depth[i] > depth[t] + 1)
			{
				depth[i] = depth[t] + 1;
				q.push(i);
				fa[i][0] = t;
				for(int j=1; j<=15; j ++)
				{
					fa[i][j] = fa[fa[i][j - 1]][j - 1];
				}
			}
		}
	}
	
}

int lca(int a, int b)
{
	if(depth[a] < depth[b]) swap(a, b);
	for(int i=15; i>=0; i--)
		if(depth[fa[a][i]] >= depth[b])
			a = fa[a][i];
	if(a == b) return a;
	
	for(int i=15; i>=0; i--)
		if(fa[a][i] != fa[b][i])
		{
			a = fa[a][i];
			b = fa[b][i];
		}
	
	return fa[a][0];
	
}

signed main()
{
	fast;
	cin >> n;
	int a, b;
	for(int i=1; i<=n; i++)
	{
		cin >> a >> b;
		if(b == -1) root = a;
		else
		{
			v[a].push_back(b);
			v[b].push_back(a);
		}
	}
	
	bfs();
	
	cin >> m;
	while(m --)
	{
		cin >> a >> b;
		int p = lca(a, b);
		if(p == a) puts("1");
		else if(p == b) puts("2");
		else puts("0");
	}
	
	return 0;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86