【C++】图论|最近公共祖先(LCA)模板

// 倍增算法
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>

using namespace std;
vector<vector<int>> fa, edg;
vector<int> depth, lg2;

void dfs(int now, int fath)
{
	fa[now][0] = fath;
	depth[now] = depth[fath] + 1;
	for (int i = 1; i <= lg2[depth[now]]; i++)
	{
		fa[now][i] = fa[fa[now][i - 1]][i - 1];
	}
	for (auto& i : edg[now])
	{
		if (i != fath) dfs(i, now);
	}
}

int lca(int x, int y)
{
	if (depth[x] < depth[y]) swap(x, y);
	while (depth[x] > depth[y])
	{
		x = fa[x][lg2[depth[x] - depth[y]] - 1];
	}
	if (x == y) return x;
	for (int k = lg2[depth[x]] - 1; k >= 0; k--)
	{
		if (fa[x][k] != fa[y][k])
		{
			x = fa[x][k];
			y = fa[y][k];
		}
	}
	return fa[x][0];
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int n, m, s, x, y;
	cin >> n >> m >> s;
	fa.resize(n + 1);
	edg.resize(n + 1);
	depth.resize(n + 1);
	lg2.resize(n + 1);
	// 预处理log2
	for (int i = 1; i <= n; i++)
	{
		lg2[i] = lg2[i - 1] + (1 << lg2[i - 1] == i);
	}
	for (auto& i : fa) i.resize(lg2[n] + 1);
	for (int i = 1; i < n; i++)
	{
		cin >> x >> y;
		edg[x].emplace_back(y);
		edg[y].emplace_back(x);
	}
	dfs(s, 0);
	while (m--)
	{
		cin >> x >> y;
		cout << lca(x, y) << endl;
	}
	return 0;
}

// Tarjan
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>

using namespace std;
vector<vector<pair<int, int>>> query;
vector<vector<int>> edg;
vector<int> fa, ans, vis;

void init(int n)
{
	fa.resize(n + 3);
	for (int i = 1; i <= n; i++)
	{
		fa[i] = i;
	}
}

int find(int x)
{
	if (x != fa[x])
	{
		fa[x] = find(fa[x]);
	}
	return fa[x];
}

void tarjan(int x)
{
	vis[x] = 1;
	for (auto& i : edg[x])
	{
		if (!vis[i])
		{
			tarjan(i);
			fa[i] = x;
		}
	}
	for (auto& i : query[x])
	{
		if (vis[i.first])
		{
			ans[i.second] = find(i.first);
		}
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int n, m, s, x, y;
	cin >> n >> m >> s;
	init(n);
	edg.resize(n + 3);
	ans.resize(n + 3);
	vis.resize(n + 3, 0);
	query.resize(n + 3);
	for (int i = 1; i < n; i++)
	{
		cin >> x >> y;
		edg[x].emplace_back(y);
		edg[y].emplace_back(x);
	}
	for (int i = 1; i <= m; i++)
	{
		cin >> x >> y;
		query[x].emplace_back(make_pair(y, i));
		query[y].emplace_back(make_pair(x, i));
	}
	tarjan(s);
	for (int i = 1; i <= m; i++)
	{
		cout << ans[i] << endl;
	}
	return 0;
}