@[20120110_linjiale](/user/1065071)
`if(size[son[v]]>size[son[u]])`
这句是什么东西？
by OldDriverTree @ 2024-02-21 17:04:30
@[OldDriverTree](/user/681036)
不好意思，是
```cpp
if(size[v]>size[son[u]])
```
by 20120110_linjiale @ 2024-02-21 17:10:56
**更新一下，代码是**
```cpp
#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+5;
int cnt;
int size[MAXN],deep[MAXN],son[MAXN],top[MAXN];
int fa[MAXN];
int n,m,root;
int from,to;
int head[MAXN*2];
struct EDGE{
int to,pre;
}edge[MAXN];
void add(int from,int to)
{
cnt++;
edge[cnt].to=to;
edge[cnt].pre=head[from];
head[from]=cnt;
return;
}
void dfs1(int u,int f)
{
size[u]=1;//以自己为根节点的子树大小
deep[u]=deep[f]+1;
for(int i=head[u];i!=0;i=edge[i].pre)
{
int v=edge[i].to;
if(v==f)
{
continue;
}
fa[v]=u;
dfs1(v,u);
size[u]+=size[v];
if(size[v]>size[son[u]])
{
son[u]=son[v];
}
}
return;
}
void dfs2(int u)
{
if(u==son[fa[u]])
{
top[u]=top[fa[u]];
}
else
{
top[u]=u;
}
for(int i=head[u];i!=0;i=edge[i].pre)
{
int v=edge[i].to;
if(v!=fa[u])
{
dfs2(v);
}
}
return;
}
int getlca(int u,int v)
{
while(top[u]!=top[v])
{
if(deep[top[u]]>deep[top[v]])
{
u=fa[top[u]];
}
else
{
v=fa[top[v]];
}
}
if(deep[u]<deep[v])
{
return u;
}
else
{
return v;
}
}
int main(){
scanf("%d%d%d",&n,&m,&root);
for(int i=1;i<n;i++)
{
scanf("%d%d",&from,&to);
add(from,to);
add(to,from);
}
dfs1(root,root);
dfs2(root);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&from,&to);
if(from==to)
{
printf("%d\n",from);
continue;
}
printf("%d\n",getlca(from,to));
}
return 0;
}
```
by 20120110_linjiale @ 2024-02-21 17:11:32
```cpp
int head[MAXN*2];
struct EDGE{
int to,pre;
}edge[MAXN];
```
和
```cpp
son[u]=son[v];
```
by Aaron_Romeo @ 2024-02-21 17:56:29