```cpp
#include<iostream>
#include<vector>
#include<cstdio>
#include<queue>
#include<map>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<set>
#include<cstring>
using namespace std;
typedef long long ll;
const ll INF=99999999;
const int N = 500010;
int n,m,s;
struct edge{
int to,ne;
}e[N];
int top[N],siz[N],son[N],fa[N],dep[N];
int head[N],ecnt = 1;
void add(int x,int y)
{
e[ecnt].to = y;
e[ecnt].ne = head[x];
head[x] = ecnt++;
}
void dfs1(int x)
{
siz[x] = 1;
dep[x] = dep[fa[x]] + 1;
for(int i = head[x];i;i = e[i].ne){
int t = e[i].to;
if(t == fa[x]) continue;
fa[t] = x;
dfs1(t);
siz[x] += siz[t];
if(!son[x]||siz[son[x]] < siz[t])
son[x] = t;
}
}
void dfs2(int x,int tp)
{
top[x] = tp;
if(son[x])
dfs2(son[x],tp);
for(int i = head[x];i;i = e[i].ne){
int t = e[i].to;
if(t == son[x]||t == fa[x]) continue;
dfs2(t,t);
}
}
int lca(int x,int y)
{
while(top[x] != top[y]){
if(dep[top[x]] >= dep[top[y]]) x = fa[top[x]];
else y = fa[top[y]];
}
return dep[x] < dep[y] ?x :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);
}
dfs1(s);
dfs2(s,s);
for(int i = 1;i <= m;i++){
int a,b;
scanf("%d%d",&a,&b);
printf("%d\n",lca(a,b));
}
return 0;
}
```
代码放错了，这个是我的
by dudujerry @ 2018-12-28 19:35:32
@[dudujerry](/space/show?uid=36502) 边开少了吧，别的都一样了。
by lol123 @ 2018-12-28 19:41:36
@[dudujerry](/space/show?uid=36502) 这种存边的方法要开2倍空间的。
by lol123 @ 2018-12-28 19:43:56
哲学
by pascalfans @ 2018-12-28 19:45:17
@[lol123](/space/show?uid=5618) 好的，我试试
by dudujerry @ 2018-12-28 19:50:06
@[lol123](/space/show?uid=5618) A掉了..调试了两个小时，感谢！
by dudujerry @ 2018-12-28 19:50:58
评测鸡不稳定？
by NaCly_Fish @ 2018-12-28 19:54:10