本模板基于codevs1503愚蠢的宠物

暴力lca：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int first[233333], next[233333], tot = 0;
bool rd[233333];
int fa[233333], sd[233333];
struct edge
{
	int from, to, cost;
}es[233333];
void init()
{
	memset(first, -1, sizeof(first));
	tot = 0;
}
void build(int f, int t)
{
	es[++tot] = (edge){f, t};
	next[tot] = first[f];
	first[f] = tot;
}
void dfs(int s)
{
	int v;
	for (int i = first[s]; i != -1; i = next[i])
	{
		v = es[i].to;
		if (!sd[v])
		{
			sd[v] = sd[s] + 1;
			fa[v] = s;
			dfs(v);
		}
	}
}
int lca(int u, int v)
{
	if (sd[u] < sd[v])
		swap(u, v);
	while (sd[u] != sd[v])
		u = fa[u];
	while (u != v)
	{
		u = fa[u];
		v = fa[v];
	}
	return u;
}
int main()
{
	init();
	int n;
	cin >> n;
	for (int i = 1; i < n; i++)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		build(u, v);
		rd[v] = 1;
	}
	for (int i = 1; i <= n; i++)
		if (!rd[i])
		{
			dfs(i);
			break;
		}
	int u, v;
	cin >> u >> v;
	cout << lca(u, v);
	return 0;
}

倍增lca：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int first[233333], next[233333], tot = 0;
int fa[233333], t[233333][30], sd[233333];
bool rd[233333];
struct edge
{
	int from, to;
}es[233333];
void init()
{
	memset(first, -1, sizeof(first));
	tot = 0;
}
void build(int f, int t)
{
	es[++tot] = (edge){f, t};
	next[tot] = first[f];
	first[f] = tot;
}
void dfs(int s)
{
	int v;
	for (int i = first[s]; i != -1; i = next[i])
	{
		v = es[i].to;
		if (!sd[v])
		{
			sd[v] = sd[s] + 1;
			fa[v] = s;
			dfs(v);
		}
	}
}
int lca(int u, int v)
{
	int i, j;
	if (sd[u] < sd[v])
		swap(u, v);
	for (i = 0; (1 << i) <= sd[u]; i++);
	i--;
	for (j = i; j >= 0; j--)
		if (sd[u] - (1 << j) >= sd[v])
			u = t[u][j];
	if (u == v)
		return u;
	for (j = i; j >= 0; j--)
	{
		if (t[u][j] != -1 && t[u][j] != t[v][j])
		{
			u = t[u][j];
			v = t[v][j];
		}
	}
	return t[u][0];
}
int main()
{
	init();
	int n;
	cin >> n;
	for (int i = 1; i < n; i++)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		build (u, v);
		rd[v] = 1;
	}
	for (int i = 1; i <= n; i++)
		if (!rd[i])
		{
			dfs(i);
			break;
		}
	for (int i = 1; i <= n; i++)
		t[i][0] = fa[i];
	int u, v;
	scanf("%d%d", &u, &v);
	for (int j = 1; j <= 20; j++)
		for (int i = 1; i <= n; i++)
			t[i][j] = t[t[i][j-1]][j-1];
	cout << lca(u, v);
	return 0;
}