@[忠诚的程序猿](/space/show?uid=78791) find的最后一行
```cpp
return y
```
改成
```cpp
return depth[x]<=depth[y]
```
by 月落落落 @ 2019-04-09 13:23:54
还有就是dfs1中搜到v时问题很大,应该这么写:
```cpp
if(v!=father[u]){
dfs1(v,u,deep+1);
size[u]+=size[v];
if(son[u]==-1||size[son[u]]<size[v])
son[u]=v;
}
```
by 月落落落 @ 2019-04-09 13:27:22
而且你没有初始化memset数组son…………
by 月落落落 @ 2019-04-09 13:27:42
问题好多…………
by 月落落落 @ 2019-04-09 13:29:40
而且空间爆了,好多没用的数组,比如rid什么的
by 月落落落 @ 2019-04-09 13:36:07
改完后的参考代码:
```cpp
#include<cstdio>
#include<iomanip>
#include<cstring>
using namespace std;
const int MAXN=1000001;
int to[MAXN],head[MAXN],next[MAXN];
inline void add(int a,int b){
static int ccnt=0;
ccnt++;
next[ccnt]=head[a];
head[a]=ccnt;
to[ccnt]=b;
}
int size[MAXN];
int son[MAXN];
int father[MAXN];
int depth[MAXN];
int top[MAXN];
void dfs1(int u,int fa,int deep){
size[u]=1;
father[u]=fa;
depth[u]=deep;
for(int i=head[u];i;i=next[i]){
int v=to[i];
if(v!=father[u]){
dfs1(v,u,deep+1);
size[u]+=size[v];
if(son[u]==-1||size[v]>size[son[u]]) son[u]=v;
}
}
}
void dfs2(int u,int t){
top[u]=t;
if(son[u]==-1)return;
dfs2(son[u],t);
for(int i=head[u];i;i=next[i]){
int v=to[i];
if(v!=son[u]&&v!=father[u]){
dfs2(v,v);
}
}
}
inline int find(int x,int y){
while(top[x]!=top[y]){
if(depth[top[x]]<depth[top[y]])swap(x,y);
x=father[top[x]];
}
return depth[x]<=depth[y]?x:y;
}
int n,m,s;
int main(){
memset(son,-1,sizeof(son));
scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<n;i++){
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
}
dfs1(s,0,0);
dfs2(s,s);
for(int i=1;i<=m;i++){
int a,b;
scanf("%d%d",&a,&b);
printf("%d\n",find(a,b));
}
return 0;
}
```
@[忠诚的程序猿](/space/show?uid=78791)
by 月落落落 @ 2019-04-09 13:36:55
@[淼淼大侠](/space/show?uid=115936) 谢谢!!!
by Fractures @ 2019-04-09 20:37:49