DFS序求LCA的模板。注释就不写了，认真上了课的人应该都能看懂。

这个写法涉及了两个技巧。

#include <bits/stdc++.h>
using namespace std;

const int N = 500010;
int n, m, s;
int tot, dfn[N], st[20][N], Log2[N];
vector<int> g[N];

void build() {
	int u, v;
	for (int i = 1; i <= n - 1; i++) {
		cin >> u >> v;
		g[u].emplace_back(v);
		g[v].emplace_back(u);
	}
}

void dfs(int u, int fa) {
	dfn[u] = ++tot;
	st[0][dfn[u]] = fa;
	for (auto v : g[u]) {
		if (v == fa) continue;
		dfs(v, u);
	}
}

inline int get(int x, int y) {
	return dfn[x] < dfn[y] ? x : y;
}

void init() {
	Log2[1] = 0;
	for (int i = 2; i <= n; i++)
		Log2[i] = Log2[i >> 1] + 1;

	for (int j = 1; j <= 18; j++)
		for (int i = 1; i + (1 << j) - 1 <= n; i++)
			st[j][i] = get(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
}

int lca(int u, int v) {
	if (u == v) return u;
	u = dfn[u], v = dfn[v];
	if (u > v) swap(u, v);
	int k = Log2[v - u];
	// 查询区间 [dfn(u)+1, dfn(v)] 内dfn最小的节点编号
	return get(st[k][u + 1], st[k][v - (1 << k) + 1]);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m >> s;
	build();
	dfs(s, 0);
	init();
	int u, v;
	while (m--) {
		cin >> u >> v;
		cout << lca(u, v) << '\n';
	}

	return 0;
}

司陆

DFS序：用DFS遍历整棵树遍历的先后顺序
时间戳：每个点被遍历到的时间
此时，我们又会发现，如果有如下一棵树： 【如果打不开，请见附录】
设lca(u,v)为W

我们会发现，在DFS序中，u到v中深度最小的那个点的父亲就是lca(u,v)。
由此，我们可以创建一个ST表，在st[0][i]存入i的父亲，并让st表以DFS序的顺序存储。由于两个点的深度差和他们父亲的深度差是一样的（父亲的深度都比自己少1），因此，这种操作即是正确的，也省了一个数组。再让数组存储当前区间深度最小的那个点的编号，就可以非常快~~~~的求出LCA了。
可是，代码还可以继续优化。可不可以把比较依据从深度改成时间戳呢？看图可以发现，lca(u,v)是以其为根的子树的节点中时间戳最小的，若设一个点vi为lca(u,v)的、在v到lca(u,v)上的最小的、lca(u,v)的儿子，又由于st表存的是自己的父亲，所以st[0][dfn[vi]]的时间戳是最小的。（CCF语言？？？） 因此，以时间戳为比较依据是可以的。

呆码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll st[500001][21];
vector<ll>edge[500001];
ll dfn[500001];
ll n,m,s,tot;
ll lg[500001];
ll get(ll a,ll b){
	return dfn[a]<dfn[b]?a:b;
}
void dfs(ll num,ll p){
	dfn[num]=++tot;
	st[dfn[num]][0]=p;
	for(auto i:edge[num]){
		if(i==p)continue;
		dfs(i,num);
	}
}
void init(){
	for(ll i=2;i<=500000;i++){
		lg[i]=lg[i>>1]+1;
	}
	dfs(s,0);
	for(ll i=1;i<=18;i++){
		for(ll j=1;j+(1<<i)-1<=n;j++){
			st[j][i]=get(st[j][i-1],st[j+(1<<(i-1))][i-1]);//以dfn为判断依据
		}
	}
}
ll lca(ll u,ll v){
	if(u==v)return u;
	u=dfn[u],v=dfn[v];
	if(u>v)swap(u,v);
	ll k=lg[v-u];
//	cout<<u<<" "<<v<<" "<<k<<"\n";
//	cout<<st[u+1][k]<<" "<<st[v-(1<<k)+1][k]<<"\n\n";
	return get(st[u+1][k],st[v-(1<<k)+1][k]);
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>m>>s;
	ll u,v;
	for(ll i=1;i<n;i++){
		cin>>u>>v;
		edge[u].emplace_back(v);
		edge[v].emplace_back(u);
	}
	init();
//	for(ll i=0;i<=5;i++){
//		for(ll j=1;j<=n;j++){
//			cout<<st[j][i]<<" ";
//		}
//		cout<<'\n';
//	}
	// for(ll i=1;i<=n;i++)cout<<dfn[i]<<" ";
	for(ll i=1;i<=m;i++){
		cin>>u>>v;
		cout<<lca(u,v)<<"\n";
	}
}

附录

1.图片打不开怎么办？
A:打开Graph Editor，复制以下内容到左侧的Graph Data，再调整一下即可（注意根节点为lca(u,v)）:

lca(u,v) B
B u
C u
D vi
lca(u,v) vi
E D
E v

A2:如果非常可惜，你的电脑连不了网络(bushi)，以上的数据也可以自己手绘。每行说明一条边，每行两个参数为两个端点。
若有错误，欢迎提出。

发个倍增解法的简单版题解，主要是提一下代码中的几个小细节。请看代码注释。

#include <bits/stdc++.h>
using namespace std;

const int N = 500010;
int n, m, s;
int anc[N][20], d[N];
vector<int> g[N];

void build() {
	int u, v;
	for (int i = 1; i <= n - 1; i++) {
		cin >> u >> v;
		g[u].emplace_back(v);
		g[v].emplace_back(u);
	}
}

void dfs(int u, int fa) {
	for (auto v : g[u]) {
		if (v == fa) continue;
		d[v] = d[u] + 1;
		anc[v][0] = u;
		dfs(v, u);
	}
}

void init() {
	for (int j = 1; j <= 18; j++)
		for (int i = 1; i <= n; i++)
			anc[i][j] = anc[anc[i][j - 1]][j - 1];
}

int lca(int u, int v) {
	if (d[u] < d[v]) swap(u, v);
	for (int i = 18; i >= 0; i--)
		// 注意这里是拿u的祖先跟v比，所以要取等号
		if (d[anc[u][i]] >= d[v])
			u = anc[u][i];
	if (u == v) return u;
	for (int i = 18; i >= 0; i--)
		if (anc[u][i] != anc[v][i])
			u = anc[u][i], v = anc[v][i];
	return anc[u][0]; // 注意返回的是u的父节点
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m >> s;
	build();
	// 重要细节！！！d[s]不能取0，因为对于无法往上跳 2^j 步的情况，
	// 用编号0来表示，而这些情况对应的d也是0（初始化）。
	d[s] = 1;
	dfs(s, 0);
	init();
	int u, v;
	while (m--) {
		cin >> u >> v;
		cout << lca(u, v) << '\n';
	}

	return 0;
}