倍增

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
int n, m, s, a, b;
vector<int>e[N];
int dep[N], fa[N][25];
void dfs(int u, int father) {
	dep[u] = dep[father] + 1;
	fa[u][0] = father;
	for (int i = 1; i <= 19; i++) {
		fa[u][i] = fa[fa[u][i - 1]][i - 1];
	}
	for (int v : e[u]) {
		if (v != father) dfs(v, u);
	}
}
int lca(int u, int v) {
	if (dep[u] < dep[v]) swap(u, v);
	for (int i = 19; i >= 0; i--) {
		if (dep[fa[u][i]] >= dep[v]) u = fa[u][i];
	}
	if (u == v) return u;
	for (int i = 19; i >= 0; i--) {
		if (fa[u][i] != fa[v][i]) {
			u = fa[u][i], v = fa[v][i];
		}
	}
	return fa[u][0];
}
int main() {
	cin>>n>>m>>s;
	for (int i = 1; i <= n - 1; i++) {
		cin>>a>>b;
		e[a].push_back(b);
		e[b].push_back(a);
	}
	dfs(s, 0);
	for (int i = 1; i <= m; i++) {
		cin>>a>>b;
		cout<<lca(a, b)<<endl;
	}
}

Tanjan

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
vector<int>e[N];
vector<pair<int, int>>query[N];
int fa[N], vis[N], ans[N], n, m, s;
int findfa(int x) {
	return fa[x] = fa[x] == x ? x : findfa(fa[x]);
}
void tarjan(int u) {
	vis[u] = true;
	for (auto v : e[u]) {
		if (!vis[v]) {
			tarjan(v);
			fa[v] = u;
		}
	}
	for (auto ak : query[u]) {
		int y = ak.first, i = ak.second;
		if (vis[y]) {
			ans[i] = findfa(y);
		}
	}
}
int main() {
	cin>>n>>m>>s;
	for (int i = 1; i <= n - 1; i++) {
		int x, y;
		cin>>x>>y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	for (int i = 1; i <= m; i++) {
		int x, y;
		cin>>x>>y;
		query[x].push_back({y, i});
		query[y].push_back({x, i});
	}
	for (int i = 1; i <= N; i++) fa[i] = i;
	tarjan(s);
	for (int i = 1; i <= m; i++) {
		cout<<ans[i]<<endl;
	}
}

树链

#include<bits/stdc++.h>
using namespace std;
const int N=500010;
vector<int> e[N];
int fa[N],dep[N],son[N],sz[N],top[N];
void dfs1(int u,int father){
    fa[u]=father,dep[u]=dep[father]+1,sz[u]=1;
    for(int v:e[u]){
        if(v==father) continue;
        dfs1(v,u);
        sz[u]+=sz[v];
        if(sz[son[u]]<sz[v]) son[u]=v;
    }
}
void dfs2(int u,int t){
    top[u]=t;
    if(!son[u]) return ;
    dfs2(son[u],t);
    for(int v:e[u]){
        if(v==fa[u]||v==son[u]) continue;
        dfs2(v,v);
    }
}
int lca(int u,int v){
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        u=fa[top[u]];
    }
    return dep[u]<dep[v]?u:v;
}
int main(){
    int n,m,s;
    cin>>n>>m>>s;
    for(int i=1;i<=n-1;i++){
        int x,y;
        cin>>x>>y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    dfs1(s,0);
    dfs2(s,s);
    while(m--){
        int a,b;
        cin>>a>>b;
        cout<<lca(a,b)<<endl;
    }
    return 0;
}