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

· · 题解

emmmmmm

这道题听说倍增不加优化会被卡。。。

所以我正好拿最近刚学的树链剖分练练手

虽然看到题解里有树剖。。。

但我自认为自己写的比较优美。。。

而且最关键的是题解里好多都在说树剖慢。。。

他们怕不是写了假的树剖。。。

下面给出严格【并不】的复杂度证明：

树剖要用到两次dfs，都是O（n）的复杂度

然后如果图是满二叉树的话是最坏情况，但此时查询也是O（logn）的

【显然最坏情况每次一步步取f[top[x]]走，走下来是一个树的深度，也就是一个logn】

所以理论复杂度上界就是O（2n+mlogn）

而且关键的是树剖常数还比倍增要小。。。

倍增的话常数虽然也很小

但是某集训队dalao写过一篇论文里面有严格的树剖的常数证明，计算结果是树剖的常数接近1/2

再加上树剖用的的空间也比倍增啊RMQ啊小

所以写树剖是完全没问题滴~

那么下面就简单说下树剖思路咯

树剖就是把树剖分成若干条不相交的链，目前常用做法是剖成轻重链

所以我们定义siz[x]为以x为根结点的子树的结点个数

对于每个结点x，在它的所有子结点中寻找一个结点y

使得对于y的兄弟节点z，都有siz[y]≥siz[z]

此时x就有一条重边连向y，有若干条轻边连向他的其他子结点【比如z】

这样的话，树上的不在重链上的边的数量就会大大减少

然后我们每次求LCA（x,y）的时候就可以判断两点是否在同一链上

如果两点在同一条链上我们只要找到这两点中深度较小的点输出就行了

如果两点不在同一条链上

那就找到深度较大的点令它等于它所在的重链链端的父节点即为x=f[top[x]]

直到两点到达同一条链上，输出两点中深度较小的点

代码如下：

//by 减维
#include<cstdio>
#include<iostream>
using namespace std;
struct edge{
    int to,ne;
}e[1000005];
int n,m,s,ecnt,head[500005],dep[500005],siz[500005],son[500005],top[500005],f[500005];
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[f[x]]+1;
    for(int i=head[x];i;i=e[i].ne)
    {
        int dd=e[i].to;
        if(dd==f[x])continue;
        f[dd]=x;
        dfs1(dd);
        siz[x]+=siz[dd];
        if(!son[x]||siz[son[x]]<siz[dd])
            son[x]=dd;
    }
}
void dfs2(int x,int tv)
{
    top[x]=tv;
    if(son[x])dfs2(son[x],tv);
    for(int i=head[x];i;i=e[i].ne)
    {
        int dd=e[i].to;
        if(dd==f[x]||dd==son[x])continue;
        dfs2(dd,dd);
    }
}
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 x,y;
        scanf("%d%d",&x,&y);
        while(top[x]!=top[y])
        {
            if(dep[top[x]]>=dep[top[y]])x=f[top[x]];
            else y=f[top[y]];
        }
        printf("%d\n",dep[x]<dep[y]?x:y);
    }
}