#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=5e5+1;
int n,m,s,a,b;
int fa[N],son[N],dep[N],top[N],sz[N];
vector<int>e[N];
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=1;
register char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
void dfs1(int x,int father)
{
fa[x]=father,dep[x]=dep[father]+1,sz[x]=1;
for(int y:e[x])
if(y!=father)
{
dfs1(y,x);
sz[x]+=sz[y];
if(sz[son[x]]<sz[y]) son[x]=y;
}
}
void dfs2(int x,int t)
{
top[x]=t;
if(!son[x]) return ;
dfs2(son[x],t);
for(int y:e[x])
if(y!=fa[x]&&y!=son[x])
dfs2(y,y);
}
int lca(int x,int y)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]]) swap(x,y);
x=fa[son[x]];
}
return dep[x]<dep[y]?x:y;
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
read(n),read(m),read(s);
for(int i=1;i<n;i++)
read(a),read(b),
e[a].push_back(b),
e[b].push_back(a);
dfs1(s,0),dfs2(s,s);
while(m--)
read(a),read(b),
cout<<lca(a,b)<<endl;
}
标签:临时,register,long,板子,int,define,getchar
From: https://www.cnblogs.com/Charlieljk/p/17902082.html