P3379 【模板】最近公共祖先（LCA）

思路：模板题思路不多说，唯一需要注意的一点是此题用vector会多耗费时间（因为内存不够会自动申请2倍内存，然后复制元素到新内存耗费时间)，用链式快很多。具体见代码。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
const int M=log2(N);
int fa[N][M],dep[N],mx,cnt=1,h[N];
struct edge{
	int to,nt;
}e[N];
void add(int u,int v){
	e[cnt].to=v;
	e[cnt].nt=h[u];
	h[u]=cnt++;
}
void dfs(int u){
	for(int i=1;i<=mx;i++)
		if(fa[u][i-1]) //如果u不存在第2^(i-1)父亲,则肯定不存在fa[u][i] 
			fa[u][i]=fa[fa[u][i-1]][i-1];
		else break;
	for(int i=h[u];i;i=e[i].nt){
		int v=e[i].to;
		if(v!=fa[u][0]){
			fa[v][0]=u;
			dep[v]=dep[u]+1;
			dfs(v);
		}
	}
}
int lca(int u,int v){
	if(dep[u]<dep[v]) swap(u,v);//默认u为较大深度的结点 
	int delta=dep[u]-dep[v];//深度差值. 
	for(int i=0;i<=mx;i++) //将u提到与v同深度 
		if((1<<i)&delta)
			u=fa[u][i];
	if(u==v) return u;//入股此时相等说明u,v的祖先就是u(v) 
	for(int i=mx;i>=0;i--)//这里要从大往小提,来达到越提越精确的效果。 
		if(fa[u][i]!=fa[v][i]) //如果父亲不相等就继续一起往上题 
		{
			u=fa[u][i];
			v=fa[v][i];
		}
	return fa[u][0];//这是u,v的父亲就是他们的LCA 
}
int main(){
	int n,m,s,a,b;
	scanf("%d%d%d",&n,&m,&s);
	mx=log2(n);//最大移动 
	for(int i=1;i<n;i++){
			scanf("%d%d",&a,&b);
			add(a,b);
			add(b,a);
	}
	dfs(s);//从根结点搜 
	while(m--){
		scanf("%d%d",&a,&b);
		printf("%d\n",lca(a,b));
	}
	return 0;
}