题解 P3379 【【模板】最近公共祖先（LCA）】

· · 题解

我发现一个严重的问题：树剖LCA写的人少，且基本都常数较大，貌似题解前六页的树剖LCA没有比我快的。 我在这里给大家讲一下树剖LCA。

首先，你要会树链剖分，如果不会请出门左转 洛谷P3384，然后我们直接两遍大法师统计信息，注意这里不用写线段树，因为我们并不需要统计权值，于是可以直接不写线段树，见图。

原谅我图画的丑

这图中蓝色和绿色的线条是重边，红色是表示我们要求这两点的LCA。

于是先判断一下，他们是不是在一条重链上，因为重链上两点的深度肯定不同，如果在同一重链上，LCA显然就是深度小的那个。我们一看，显然不同，于是我们可以想到将情况转化为在同一重链上来做。首先比较一下谁的链顶深度大，就向上跳。

我们给两点起个名字：x,y,从图中可以显然的看出（注意：轻儿子的链顶是他自己）：depth[top[x]]>depth[top[y]]（depth是深度）。 于是我们把y向上跳，即y=fa[top[y]]（fa是父亲），发现他们在一条重链上了，就转化成了第一种情况，返回深度小的点即可。 贴一下核心代码：

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）

#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;
}