最近公共祖先（LCA）

倍增求lca

#include
using namespace std;
const int logn=19,maxn=5e5+5;
int d[maxn];
vectoru[maxn];
int n,m,x,y,f[maxn][logn],root;
void dfs(int now,int last)
{
	d[now]=d[last]+1;
	f[now][0]=last;
	for(int i=1;id[w])swap(u,w);
	for(int i=logn-1;i>=0;i--)
		if(d[u]<=d[f[w][i]])w=f[w][i];
	for(int i=logn-1;i>=0;i--){
		if(f[u][i]==f[w][i])continue;
		u=f[u][i];
		w=f[w][i];
	}
	if(u==w)return u;
	return f[u][0];
}	
int main()
{
	scanf("%d%d%d",&n,&m,&root);
	for(int i=1;i<=n-1;i++)
	{
		scanf("%d%d",&x,&y);
		u[x].push_back(y);
		u[y].push_back(x);
	}
	dfs(root,root);
	while(m--)
	{
		scanf("%d%d",&x,&y);
//		cout< 
Tarjan求lca
 
//Tarjan
#include
using namespace std;
const int maxn=5e5+5;
int n,m,x,y,f[maxn],ans[maxn],root;
vectoru[maxn],pos[maxn],qs[maxn];
bool vis[maxn];
int getf(int now)
{
	if(f[now]==now)return now;
	return f[now]=getf(f[now]);
}
void Tarjan(int now,int last)
{
	for(int i=0;i 
dfs序求lca
 
//dfs序 
#include
using namespace std;
const int maxn=5e5+5,logn=19;
int d[maxn],f[maxn][logn+2],T[maxn*2],t[maxn][3],len=0,n,m,x,y,root;
vectoru[maxn];
void dfs(int now,int last)
{
	d[now]=d[last]+1;
	f[now][0]=last;
	for(int i=1;id[v])swap(u,v);
	if(t[u][0]<=t[v][0]&&t[v][1]<=t[u][1])
		return u;
	for(int i=logn-1;i>=0;i--)
	{
		if(!(t[f[v][i]][0]<=t[u][0]&&t[u][1]<=t[f[v][i]][1]))
		v=f[v][i];
	}
	return f[v][0];
}
int main()
{
	scanf("%d%d%d",&n,&m,&root);
	for(int i=1;i 
题目：https://www.luogu.com.cn/problem/P3379