不介意的话您可以参考一下我的代码：
```
#include<bits/stdc++.h>
#define MAXN 500015
#define MAXM MAXN-1
using namespace std;
int n,m,s,max0;
int tot,head[MAXN<<1],dep[MAXN<<1];
int fa[MAXN<<1][40];
struct node{
int u,v;
int next;
}edge[MAXM<<1];
void addedge(int x,int y)
{
edge[++tot].u=x;
edge[tot].v=y;
edge[tot].next=head[x];
head[x]=tot;
}
void dfs(int x)
{
for(int i=1;i<=max0;i++)
if(fa[x][i-1]) fa[x][i]=fa[fa[x][i-1]][i-1];
else break;
for(int i=head[x];i;i=edge[i].next)
{
int y=edge[i].v;
if(y!=fa[x][0]){
fa[y][0]=x;
dep[y]=dep[x]+1;
dfs(y);
}
}
}
int LCA(int u,int v)
{
if(dep[u]<dep[v])swap(u,v);
int delta=dep[u]-dep[v];
for(int x=0;x<=max0;x++)
if((1<<x)&delta)u=fa[u][x];
if(u==v)return u;
for(int x=max0;x>=0;x--)
if(fa[u][x]!=fa[v][x])
{
u=fa[u][x];
v=fa[v][x];
}
return fa[u][0];
}
int main()
{
scanf("%d%d%d",&n,&m,&s);
max0=(int)(log(n)/log(2))+5;
int x,y;
for(int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
addedge(x,y);
addedge(y,x);
}
dfs(s);
int a,b;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
printf("%d\n",LCA(a,b));
}
return 0;
}
```
by xiangling @ 2018-07-20 10:14:28
大佬，你能告诉我我哪里错了么??
by zhou_yk @ 2018-07-23 14:48:16
@[rainman](/space/show?uid=55804) 我稍微改了一下,但还是错的,还是70分,但1个TLE,两个Wa!
#1
AC
0ms/2445KB
#2
TLE
#3
AC
0ms/2304KB
#4
AC
0ms/2238KB
#5
AC
12ms/3421KB
#6
AC
8ms/3429KB
#7
AC
12ms/3507KB
#8
AC
12ms/3351KB
#9
WA
#10
WA
```cpp
#include <bits/stdc++.h>
using namespace std;
int n,m,size,s,x,y,u,v,tot,maxo,j;
int next[1000005],head[1000005],fa[1000005],d[1000005],f[1000005][21],vet[1000005];
bool vis[1000005];
void add(int u,int v)
{
size++;
next[size]=head[u];
head[u]=size;
vet[size]=v;
}
void dfs(int root,int depth)
{
d[root]=depth;vis[root]=1;
for (int i=head[root];i!=0;i=next[i])
{
if (vis[vet[i]]!=0) continue;
fa[vet[i]]=root;
dfs(vet[i],depth+1);
}
}
int lca(int u,int v)
{
if (d[u]<d[v]) swap(u,v);
int de=d[u]-d[v];
for(int i=0;i<=maxo;i++) if ((1<<i)&de) u=f[u][i];
if (u==v) return u;
for (int i=maxo;i>=0;i--)
if (f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i];
return fa[u];
}
int main()
{
scanf("%d%d%d",&n,&m,&s);
maxo=(int)(log(n)/log(2))+5;
for (int i=1;i<n;i++) {
scanf("%d%d",&x,&y);
add(x,y);add(y,x);
}
dfs(s,0);
for(int i=1;i<=n;i++) f[i][0]=fa[i];
j=1;
while (1<<j<=n)
{
for(int i=1;i<=n;i++)
f[i][j]=f[f[i][j-1]][j-1];
j++;
}
for (int i=1;i<=m;i++)
{
scanf("%d%d",&u,&v);
printf("%d\n",lca(u,v));
}
return 0;
}
```
by zhou_yk @ 2018-07-23 15:17:45