题解|lca模板

树剖真的快

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=5e5+5,M=1e6+5;
int n,root;
int h[N],e[M],ne[M],idx;
int fa[N],dep[N],sze[N],son[N];
int dfn[N],rnk[N],top[N],cnt;
void add(int x,int y) {
	e[idx]=y,ne[idx]=h[x],h[x]=idx++;
}
void dfs1(int u,int f) {
	fa[u]=f;
	dep[u]=dep[f]+1;
	sze[u]=1;
	son[u]=-1;
	for (int i=h[u];~i;i=ne[i]) {
		int v=e[i];
		if (v==f) continue;
		dfs1(v,u);
		sze[u]+=sze[v];
		if (son[u]==-1||sze[son[u]]<sze[v]) {
			son[u]=v;
		}
	}
}
void dfs2(int u,int t) {
	dfn[u]=++cnt;
	rnk[cnt]=u;
	top[u]=t;
	if (son[u]==-1) return;
	dfs2(son[u],t);
	for (int i=h[u];~i;i=ne[i]) {
		int v=e[i];
		if (v==fa[u]||v==son[u]) continue;
		dfs2(v,v);
	}
}
int lca(int x,int y) {
	while (top[x]!=top[y]) {
		if (dep[top[x]]<dep[top[y]]) {
			swap(x,y);
		}
		x=fa[top[x]];
	}
	if (dep[x]>dep[y]) {
		swap(x,y);
	}
	return x;
}
int main() {
	memset(h,-1,sizeof h);
	int q;
	scanf("%d %d %d",&n,&q,&root);
	for (int i=1;i<n;i++) {
		int x,y;
		scanf("%d %d",&x,&y);
		add(x,y);
		add(y,x);
	}	
	dfs1(root,0);
	dfs2(root,root);
	while (q--) {
		int x,y;
		scanf("%d %d",&x,&y);
		printf("%d\n",lca(x,y));
	}
	return 0;
}