RT,禁止无意义回复
#pragma GCC optimize("Ofast","-funroll-loops","-fdelete-null-pointer-checks")
#pragma GCC target("ssse3","sse3","sse2","sse","avx2","avx")
#include<bits/stdc++.h>
using namespace std;
const int maxn=500005;
int depth[maxn];
int fa[maxn][25],head[maxn];
double log2n;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21], *p1 = buf, *p2 = buf;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*f;
}
inline void print(int x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) print(x/10);
putchar(x%10+'0');
}
struct node
{
int next,to;
}edge[maxn<<1];
int cnt=0;
void add_edge(int u,int v)
{
edge[++cnt].to=v;
edge[cnt].next=head[u];
head[u]=cnt;
}
inline void getdepth(int now,int father)
{
depth[now]=depth[father]+1;
fa[now][0]=father;
for(int i=1;(1<<i)<=depth[now];i++) fa[now][i]=fa[fa[now][i-1]][i-1];
for(int i=head[now];i;i=edge[i].next)
{
if(edge[i].to==father)continue;
getdepth(edge[i].to,now);
}
}
inline int LCA(int u,int v)
{
int deepv=depth[v],deepu=depth[u];
if(depth[v]!=depth[u])
{
if(depth[v]>depth[u]){
swap(u,v);
swap(deepv,deepu);
}
int d=deepu-deepv;
for(int i=0;i<=log2n;i++)
if((1<<i)&d)u=fa[u][i];
}
for(int i=log2n;i>=0;i--)
{
if(depth[fa[u][i]]<=0)continue;
if(fa[u][i]==fa[v][i])continue;
else u=fa[u][i],v=fa[v][i];
}
return fa[u][0];
}
int main()
{
int n,m,hd;
n=read();m=read();hd=read();
for(int i=1;i<=n;i++)
{
int u,v;u=read();v=read();
add_edge(u,v);add_edge(v,u);
}
getdepth(hd,0);
log2n=log2(n)/log2(2)+0.5;
for(int i=1;i<=m;i++)
{
int u,v;u=read();v=read();
print(LCA(u,v));putchar('\n');
}
}
好像问题是跳不出循环/fad