首先通过DFS求出深度和父亲，有了 $fa[i]$ ，才能利用倍增求出 $anc[i][j]$

int dep[N], fa[N];
void dfs(int x, int father)
{
    fa[x] = father;
    dep[x] = dep[father] + 1; // 每个点的深度等于父节点的深度+1
    for (auto i:G[x])
        if (i != father) 
            dfs(i, x);
}

之后，预处理anc[i][j]：

节点 $i$ 向上走 $2^j$ 步，分两步：先走 $2^{j-1}$, 到达 $anc[i][j-1]$ ,在此基础上，再走$2^{j-1}$，$anc[anc[i][j-1]][j-1]$

void preprocess()
{
	for (int i = 1; i <= n; i++)
		anc[i][0] = fa[i];
	for (int j = 1; (1 << j) <= n; j++)
		for (int i = 1; i <= n; i++)
			anc[i][j] = anc[anc[i][j - 1]][j - 1];
}

预处理结束

查找的过程中，分两步

第一步是跳到同一个层级，做法是，只有深度大的向上跳

利用二进制的思想，假设深度差为 13 ，转换为二进制为 1101

我们可以看出来，分别需要跳 8、4、1 步，即 $2^3、2^2、2^0$

依次执行

x = anc[x][3]

x = anc[x][2]

x = anc[x][0]

就走到了深度相同的位置

代码实现中，从大到小依次尝试 $2^j$, 如果能跳，则跳，最终就会到达深度相同的位置

int LCA(int p, int q)
{
	if (dep[p] < dep[q])
		swap(p, q);
	for (int i = 19; i >= 0; i--)
		if (dep[p] - (1 << i) >= dep[q])
			p = anc[p][i];
}

第二步是两个点同步向上跳，跳到离公共祖先最近的点

int LCA(int p, int q)
{
	if (dep[p] < dep[q])
		swap(p, q);
	for (int i = 19; i >= 0; i--)
		if (dep[p] - (1 << i) >= dep[q])
			p = anc[p][i];
	if (p == q)
		return p; // LCA为p
	for (int i = 19; i >= 0; i--)
		if (anc[p][i] && anc[p][i] != anc[q][i])
		{
			p = anc[p][i];
			q = anc[q][i];
		}
	return fa[p]; // LCA为fa[p]
}