题解 P3379 【【模板】最近公共祖先（LCA）】
空銀子
2019-10-04 15:54:04
我发现一个严重的问题：树剖LCA写的人少，且基本都常数较大，貌似题解前六页的树剖LCA没有比我快的。
我在这里给大家讲一下树剖LCA。
首先，你要会树链剖分，如果不会请出门左转
[洛谷P3384](https://www.luogu.org/problem/P3384)，然后我们直接两遍大法师统计信息，注意这里不用写线段树，因为我们并不需要统计权值，于是可以直接不写线段树，见图。
**原谅我图画的丑**
这图中蓝色和绿色的线条是重边，红色是表示我们要求这两点的LCA。
于是先判断一下，他们是不是在一条重链上，因为重链上两点的深度肯定不同，如果在同一重链上，LCA显然就是深度小的那个。我们一看，显然不同，于是我们可以想到将情况转化为在同一重链上来做。首先比较一下谁的链顶深度大，就向上跳。
我们给两点起个名字：x,y,从图中可以显然的看出（注意：轻儿子的链顶是他自己）：depth[top[x]]>depth[top[y]]（depth是深度）。
于是我们把y向上跳，即y=fa[top[y]]（fa是父亲），发现他们在一条重链上了，就转化成了第一种情况，返回深度小的点即可。
贴一下核心代码：
```cpp
int query(int x,int y)//核心代码
{
while(top[x]!=top[y])//判断是否在一条重链上
if(depth[top[x]]>=depth[top[y]])//链顶深度大的往上跳
x=fa[top[x]];
else
y=fa[top[y]];
return depth[x]<depth[y]?x:y;//返回深度小的节点编号
}
```
最后再贴一下AC代码（最大的点380ms，总共1.03s）
```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN=500005;
struct Edge
{
int from;
int to;
int next;
}e[MAXN<<1];//邻接表存图
int depth[MAXN],fa[MAXN],siz[MAXN],head[MAXN],son[MAXN],root,n,opt,cnt,top[MAXN];//son是重儿子，siz是子树大小，opt是询问数，其他同上文。
inline int read(void)//快读
{
char ch=getchar();
int mark=1,x=0;
while((ch<'0'||ch>'9')&&ch!='-')
ch=getchar();
if(ch=='-')
{
mark=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x*10)+(ch-'0');
ch=getchar();
}
return mark*x;
}
void dfs1(int p,int dep,int father)//统计子树大小、深度、父亲和重儿子。
{
depth[p]=dep;
fa[p]=father;
int maxv=-1;
siz[p]=1;
for(int i=head[p];i;i=e[i].next)
if(e[i].to!=father)
{
dfs1(e[i].to,dep+1,p);
siz[p]+=siz[e[i].to];
if(siz[e[i].to]>maxv)
{
maxv=siz[e[i].to];
son[p]=e[i].to;
}
}
return ;
}
void dfs2(int p,int tp)//统计链顶
{
top[p]=tp;
if(!son[p])
return ;
dfs2(son[p],tp);
for(int i=head[p];i;i=e[i].next)
if(e[i].to!=fa[p]&&e[i].to!=son[p])
dfs2(e[i].to,e[i].to);
return ;
}
int query(int x,int y)//核心代码
{
while(top[x]!=top[y])//判断是否在一条重链上
if(depth[top[x]]>=depth[top[y]])//链顶深度大的往上跳
x=fa[top[x]];
else
y=fa[top[y]];
return depth[x]<depth[y]?x:y;//返回深度小的节点编号
}
void add(int u,int v)//加边
{
e[++cnt].from=u;
e[cnt].to=v;
e[cnt].next=head[u];
head[u]=cnt;
e[++cnt].from=v;
e[cnt].to=u;
e[cnt].next=head[v];
head[v]=cnt;
return ;
}
int main(void)//主函数
{
n=read(),opt=read(),root=read();
for(int i=1;i<n;i++)
add(read(),read());
dfs1(root,0,root);
dfs2(root,root);
while(opt--)
printf("%d\n",query(read(),read()));
return 0;
}
```