最近公共祖先

AisDaeun 7 2023-10-29

定义

给定一颗有根树,若节点z既是节点x的祖先,又是节点y的祖先,则称z是x,y的公共祖先。深度最大的公共祖先就叫做x,y的最近公共祖先(LCA),记为LCA(x, y)。

求LCA的方法

主要有以下几种:向上标记法、树上倍增法、树链剖分法、Tarjan算法。

向上标记法就是朴素方法,tarjan是把询问离线下来后的向上标记法;
树上倍增法、树链剖分法都是log级别的,其中树链剖分法常数更小、不容易被卡。

树上倍增法

设d[i]表示从树根到i的距离,即i点的深度;

设f[i][j]表示从点i出发,走 2^j 步能够到达的祖先的深度。

首先进行O(n \log n)的预处理,可得以下转移方程式:

f[i][j] = f[f[i][j - 1][j - 1]

显然成立,即从i点向上走 2^{j - 1} 步的点向上走 2^{j - 1} 步,就是i点向上走 2^j 步能够到达的祖先的深度。

每次查询时,

模板题:洛谷 P3379

#include <bits/stdc++.h>
#define _for(i, a, b) for (int i = (a); i <= (b); ++i)
#define __for(i, a, b) for (int i = (a); i >= (b); --i)
int read() {
	int x = 0; bool fl(0); char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) fl = ch == '-';
	for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
	return fl ? -x : x;
}
const int N = 500010, M = 1000010;
int head[N], next[M], ver[M], tot;
void add(int x, int y) {
	ver[++tot] = y, next[tot] = head[x], head[x] = tot;
}
int d[N], f[N][20], t;
void bfs(int s) {
	std::queue<int> q;
	q.push(s); d[s] = 1;
	while (!q.empty()) {
		int x = q.front(); q.pop();
		for (int i = head[x]; i; i = next[i]) {
			int y = ver[i];
			if (d[y]) continue;
			d[y] = d[x] + 1;
			f[y][0] = x;
			_for(j, 1, t) f[y][j] = f[f[y][j - 1]][j - 1];
			q.push(y);
		}
	}
}
int lca(int x, int y) {
	if (d[x] > d[y]) std::swap(x, y);
	__for(i, t, 0) if (d[f[y][i]] >= d[x]) y = f[y][i];
	if (x == y) return x;
	__for(i, t, 0) if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
	return f[x][0];
}
signed main() {
	std::ios::sync_with_stdio(false);
	int n = read(), m = read(), s = read();
	_for(i, 1, n - 1) {
		int x = read(), y = read();
		add(x, y), add(y, x);
	}
	t = (int) (std::log(n) / std::log(2)) + 1;
	bfs(s);
	_for(i, 1, m) {
		int a = read(), b = read();
		std::cout << lca(a, b) << '\n';
	}
	return 0;
}