本地运行挺好的呀,下载了第一个数据,运行也立刻出结果(放在IDE上也一样)。求差错qwq:
#include <iostream>
#include <cstdio>
#define maxlog 20
using namespace std;
const int MAX = 500050;
int n,m,s,cnt,head[MAX],dep[MAX],f[MAX][25];
struct node
{
int to,nxt;
} edge[MAX];
void _add (int x,int y);
int pre (int x,int father);
int LCA (int x,int y);
int main ()
{
scanf ("%d%d%d",&n,&m,&s);
for (int i = 1;i < n;++i)
{
int x,y;scanf ("%d%d",&x,&y);
_add (x,y);_add (y,x);
}
//for (int i = 1;i <= cnt;++i) cout<<edge[i].nxt<<" "<<edge[i].to<<" "<<head[i]<<endl;
pre (s,0);
//for (int i = 1;i <= n;++i) cout<<dep[i]<<endl;
for (int i = 1;i <= m;++i)
{
int x,y;scanf ("%d%d",&x,&y);
printf ("%d\n",LCA (x,y));
}
return 0;
}
void _add (int x,int y)
{
edge[++cnt].to = y;
edge[cnt].nxt = head[x];
head[x] = cnt;
}
int pre (int x,int father)
{
f[x][0] = father;//x 的父结点为 father
dep[x] = dep[father] + 1;
//f[i][j] 表示 i 的第 2 ^ j 辈祖先
//f[i][j] = f[f[i][j - 1][j - 1]
for (int i = 0;i < maxlog;++i) f[x][i + 1] = f[f[x][i]][i];
for (int i = head[x];i;i = edge[i].nxt)
if (edge[i].to != father) pre (edge[i].to,x);
}
int LCA (int x,int y)
{
if (dep[x] < dep[y]) swap (x,y);//保持 x 的深度大于 y 的
for (int i = maxlog;i >= 0;--i)
{
if (dep[f[x][i]] >= dep[y]) x = f[x][i];//变为同一层
if (x == y) return x;//已经找到
}
for (int i = maxlog;i >= 0;--i)
{
if (f[x][i] != f[y][i])//如果不是同一个祖先
x = f[x][i],y = f[y][i];
}
return f[x][0];//LCA 子结点
}