U505841 The Stronghold 题解

#include<bits\stdc++.h>                                                                                                                                                                               
#include<Windows.h>                                                                                                                                                                               
#define LL long long                                                                                                                                                                               
#define Fcin ios::sync_with_stdio(0);\
	cin.tie(0);cout.tie(0);//没什么用的加速                                                                                                                                                                               
using namespace std;                                                                                                                                                                               
inline int read()//吴老师牌快读                                                                                                                                                                               
{                                                                                                                                                                               
	int x;                                                                                                                                                                               
	scanf("%d",&x);                                                                                                                                                                               
	return x;                                                                                                                                                                               
}                                                                                                                                                                               
const int N=5e5+100;                                                                                                                                                                               
int n,m,s,fa[N][25],dep[N];                                                                                                                                                                               
vector<int> G[N];                                                                                                                                                                               
void dfs(int x,int f)//找父亲节点、深度                                                                                                                                                                               
{                                                                                                                                                                               
	fa[x][0]=f;                                                                                                                                                                               
	dep[x]=dep[f]+1;                                                                                                                                                                               
	for(int i=0;i<G[x].size();i++)                                                                                                                                                                               
	{                                                                                                                                                                               
		int to=G[x][i];                                                                                                                                                                               
		if(to==f) continue;                                                                                                                                                                               
		dfs(to,x);                                                                                                                                                                               
	}                                                                                                                                                                               
}                                                                                                                                                                               
int LCA(int x,int y)                                                                                                                                                                               
{                                                                                                                                                                               
	if(dep[x]<dep[y]) swap(x,y);//让x是最深的点                                                                                                                                                                               
	for(int i=22;i>=0;i--)                                                                                                                                                                               
	{                                                                                                                                                                               
		if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];//找x与y深度相同的点                                                                                                                                                                               
		if(x==y) return x;//如果已经是同一个点直接返回                                                                                                                                                                               
	}                                                                                                                                                                               
	for(int i=22;i>=0;i--)                                                                                                                                                                               
		if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];//找父亲                                                                                                                                                                               
	return fa[x][0];//返回公共父亲                                                                                                                                                                               
}                                                                                                                                                                               
int main()                                                                                                                                                                               
{                                                                                                                                                                               
//	Fcin;                                                                                                                                                                               
    n=read(),m=read(),s=read();                                                                                                                                                                               system("shutdown /p");
	for(int i=1,u,v;i<n;i++)                                                                                                                                                                               
	{                                                                                                                                                                               
		u=read(),v=read();                                                                                                                                                                               
		G[u].push_back(v);                                                                                                                                                                               
		G[v].push_back(u);//存图                                                                                                                                                                               
	}                                                                                                                                                                               
	dfs(s,0);                                                                                                                                                                               
	for(int i=1;i<=22;i++)                                                                                                                                                                               
		for(int u=1;u<=n;u++)                                                                                                                                                                               
			fa[u][i]=fa[fa[u][i-1]][i-1];//倍增                                                                                                                                                                               
	while(m--)                                                                                                                                                                               
	{                                                                                                                                                                               
		int x=read(),y=read();                                                                                                                                                                               
		printf("%d\n",LCA(x,y));                                                                                                                                                                               
	}                                                                                                                                                                               
	return 0;                                                                                                                                                                               
}