03 最近公共祖先（LCA）：倍增解法

最近公共祖先（LCA）问题——倍增解法

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

题目描述

如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。

输入格式

第一行包含三个正整数 $N,M,S$，分别表示树的结点个数、询问的个数和树根结点的序号。

接下来 $N-1$ 行每行包含两个正整数 $x, y$，表示 $x$ 结点和 $y$ 结点之间有一条直接连接的边（数据保证可以构成树）。

接下来 $M$ 行每行包含两个正整数 $a, b$，表示询问 $a$ 结点和 $b$ 结点的最近公共祖先。

输出格式

输出包含 $M$ 行，每行包含一个正整数，依次为每一个询问的结果。

样例 #1

样例输入 #1

5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5

样例输出 #1

4
4
1
4
4

提示

对于 $30\%$ 的数据，$N\leq 10$，$M\leq 10$。

对于 $70\%$ 的数据，$N\leq 10000$，$M\leq 10000$。

对于 $100\%$ 的数据，$1 \leq N,M\leq 500000$，$1 \leq x, y,a ,b \leq N$，不保证 $a \neq b$。

样例说明：

该树结构如下：

第一次询问：$2, 4$ 的最近公共祖先，故为 $4$。

第二次询问：$3, 2$ 的最近公共祖先，故为 $4$。

第三次询问：$3, 5$ 的最近公共祖先，故为 $1$。

第四次询问：$1, 2$ 的最近公共祖先，故为 $4$。

第五次询问：$4, 5$ 的最近公共祖先，故为 $4$。

故输出依次为 $4, 4, 1, 4, 4$。

• 倍增算法求LCA

第一步：预处理对数表数组

如果我们预处理一个数组，规定：lg2[i]表示log_2^i+1（别问为什么加一，不然不方便在O(n)的时间内求出，用到的时候-1即可）

使得：对数可以查表获得，则大大方便：

for(int i=1;i<=n;i++)//deal array:lg2[i]+1
    {
        lg2[i]=lg2[i-1]+(1<<lg2[i-1]==i);
    }

处理方法自己推：

lg2[1]:1 lg2[2]:2 lg2[3]:2 lg2[4]:3 lg2[5]:3 
lg2[6]:3 lg2[7]:3 lg2[8]:4 lg2[9]:4 lg2[10]:4
lg2[11]:4 lg2[12]:4 lg2[13]:4 lg2[14]:4 lg2[15]:4
lg2[16]:5 lg2[17]:5 lg2[18]:5 lg2[19]:5 lg2[20]:5

解释如下：（ai生成，有删改）

这段代码定义了一个名为lg2的数组,用于计算以2为底的对数+1。具体来说,lg2[i]表示数字i的以2为底的对数+1的值。

在循环中,首先将lg2[0]赋值为0。然后,对于每个i(从1到n),将lg2[i]的值设置为lg2[i-1]+(1<<lg2[i-1]==i)。

这个循环的目的是计算2的整数次幂在lg2数组中的对应位置。具体来说,(1<<lg2[i-1])表示2的i-1次方,==i表示i是2的i-1次方的整数次幂。如果i是2的i-1次方的整数次幂,那么(1<<lg2[i-1])==i,否则(1<<lg2[i-1])!=i。因此,(1<<lg2[i-1]==i)的值为1或0,可以用来判断i是否是2的i-1次方的整数次幂。

最后,lg2[i]表示数字i的以2为底的对数+1,即log_2(i)+1。

第二步：通过一次dfs，预处理找2的i次方祖先数组fa和深度数组depth，后面会有用

void predfs(int nowpoint,int father=0)
{//每递归到一个节点nowpoint,就完成nowpoint节点的depth[nowpoint]和
//nowpoint的最高能跳到的2的i次方级祖先的编纂
    depth[nowpoint]=depth[father]+1;
//nowpoint的深度比其父的深度大1
    fa[nowpoint][0]=father;
//nowpoint的2的0次方级祖先，即nowpoint的1级祖先为父亲节点
    for(int i=1;i<=lg2[depth[nowpoint]];i++)
    {//这个循环跑遍了nowpoint能大跃进到的每一个祖先节点的可能性
        fa[nowpoint][i]=fa[fa[nowpoint][i-1]][i-1];
 //意思是now的2^i祖先等于now的2^(i-1)祖先的2^(i-1)祖先
//例如：nowpoint的4级祖先等于nowpoint的2级祖先的2级祖先
    }
    for(auto ip :ipoint[nowpoint] )
    {//遍历nowpoint的子节点，继续编纂
        if(ip!=father)
        {
            predfs(ip,nowpoint);
        }
    }
}

第三步，理解LCA算法：

以下开始正式说明：倍增算法 原理视频：https://www.bilibili.com/video/BV1nE411L7rz?vd_source=c6cac99ae3e57c727ad51765bee0a508

所谓倍增，就是按2的倍数来增大，也就是跳 1,2,4,8,16,32 …… 不过在这我们不是按从小到大跳，而是从大向小跳，即按……32,16,8,4,2,1来跳，如果大的跳不过去，再把它调小。这是因为从小开始跳，可能会出现“悔棋”的现象。拿 5 为例，从小向大跳，5=1+2+4,所以我们还要回溯一步，然后才能得出5=1+4；而从大向小跳，直接可以得出5=4+1。

如图：节点19的深度depth[19]=13，节点2的深度depth[2]=2

（如果认为0号节点深度为0的话）

则18号节点称为19号节点的1级祖先，即为$2^0$级祖先

同理：17号节点称为19号节点的2级祖先，即为$2^1$级祖先

同理：15号节点称为19号节点的4级祖先，即为$2^2$级祖先

同理：11号节点称为19号节点的8级祖先，即为$2^3$级祖先

所以如果有这样一种可能，一次性跳到 $2^{…32,16,8,4,2,1}$ 级祖先，则加快效率

一：使得蓝色箭头经过：先跳越$2^3$次（3这个数字通过：$floor(log_2^{depth[19]-depth[2]})$得到，本来理想状况下跳跃depth[19]-depth[2]=13-2=11个节点，由于要用2的……4，3，2，1次方去逼近最终取等depth[19]-depth[2]这个差值）

二：此时蓝色箭头已经跳跃到了11号点，再跳跃$2^{floor(log_2^{depth[11]-depth[2]})}$ 个点，即$2^1$=2个点，同理，再跳$2^0$=1个点，到3号点。于是此时：箭头与2就处于相同深度（如下图所示）

特判：此时，箭头与2就处于相同深度，如果此时，箭头恰好指向2号节点，即证明19号节点为2号节点的子节点，所以LCA为2号节点，直接返回2号节点作为结果

如果以上特判不成立：

三：下面开始做尝试，让两个端点（2，3节点）同时向上跳跃，优先尝试跳跃$2^1$（因为最多也只能向上跳这么多）再尝试跳跃$2^0$ 个，再尝试不跳越。看何时有跳跃后节点不重合情况（因为如下图：0号点和1号点都是2，3点的Common Ancester，所以重合并不能作为判断条件，而是应该寻找非重合的深度最浅的两点（在下图中不用跳即可到达这两点，即这两点恰好为2，3），让2，3处的箭头跳到这两个点，即有：这两个新确定的点的公共父节点为LCA）

int LCA(int x,int y)
{
    if(depth[x]<depth[y])
    {
        swap(x,y);
    }
//以上特判，用数学语言来说就是：不妨设x的深度 >= y的深度
    while(depth[x]>depth[y])
    {
        x=fa[x][lg2[depth[x]-depth[y]]-1];
    } //先跳到同一深度
    if(x==y)return x;//如果x是y的祖先，那他们的LCA肯定就是x了
    else
    {
        for(int i=lg2[depth[x]]-1;i>=0;--i)//不断向上跳（lg就是之前说的常数优化）
        {
            if(fa[x][i]!=fa[y][i])
            { //因为我们要跳到它们LCA的下面一层，所以它们肯定不相等，如果不相等就跳过去。
                x=fa[x][i];
                y=fa[y][i];
            }
        }
    }
    return fa[x][0];//返回父节点
}

完整代码（100unaccepted）

#include<iostream>
#include<vector>
#define int long long
using namespace std;
const int N=5e5+5;
vector<int> ipoint[N];
int u,a[N]={0};
int lg2[N]={0},depth[N],father[N][22];
void dfs(int nowpoint,int fa=0)
{
    depth[nowpoint]=depth[fa]+1;
    father[nowpoint][0]=fa;
    for(int i=1;i<=lg2[depth[nowpoint]]-1;i++)
    {
        father[nowpoint][i]=father[father[nowpoint][i-1]][i-1];
    }
    for(auto ip:ipoint[nowpoint])
    {
        if(ip!=fa)
            dfs(ip,nowpoint);
    }
    return;
}
int LCA(int x, int y)
{
    if(depth[x]<depth[y])
    {
        swap(x,y);
    }
    while(depth[x]>depth[y])
    {
        x=father[x][lg2[depth[x]-depth[y]]-1];
    }
    if(x==y)return x;
    for(int i=lg2[depth[x]]-1;i>=0;i--)
    {
        if(father[x][i]!=father[y][i])
        {
            x=father[x][i];
            y=father[y][i];
        }
    }
    return father[x][0];
}
signed main(void)
{

    int n,m,s,edge1,edge2;
    cin>>n>>m>>s;
    for(int i=1;i<=n;i++)//deal array:lg2[i]+1
    {
        lg2[i]=lg2[i-1]+(1<<lg2[i-1]==i);
    }
    for(int i=1;i<=n-1;i++)
    {
        scanf("%d %d", &edge1, &edge2);
        ipoint[edge1].emplace_back(edge2);
        ipoint[edge2].emplace_back(edge1);
    }
    dfs(s);
    while(m--)
    {
        scanf("%d %d",&edge1,&edge2);
        cout<<LCA(edge1,edge2)<<endl;
    }

    return 0;
}

LCA解决：树上两点距离公式

lca处理树上任意两点间距离，即：dis[a]+dis[b]-2*dis[lca(a,b)]

LCA解决：树上路径相交问题

例题如下：

仓鼠找 sugar

题目描述

小仓鼠的和他的基（mei）友（zi）sugar 住在地下洞穴中，每个节点的编号为 $1\sim n$。地下洞穴是一个树形结构。这一天小仓鼠打算从从他的卧室（$a$）到餐厅（$b$），而他的基友同时要从他的卧室（$c$）到图书馆（$d$）。他们都会走最短路径。现在小仓鼠希望知道，有没有可能在某个地方，可以碰到他的基友？

小仓鼠那么弱，还要天天被 zzq 大爷虐，请你快来救救他吧！

输入格式

第一行两个正整数 $n$ 和 $q$，表示这棵树节点的个数和询问的个数。

接下来 $n-1$ 行，每行两个正整数 $u$ 和 $v$，表示节点 $u$ 到节点 $v$ 之间有一条边。

接下来 $q$ 行，每行四个正整数 $a$、$b$、$c$ 和 $d$，表示节点编号，也就是一次询问，其意义如上。

输出格式

对于每个询问，如果有公共点，输出大写字母 Y；否则输出N。

样例 #1

样例输入 #1

5 5
2 5
4 2
1 3
1 4
5 1 5 1
2 2 1 4
4 1 3 4
3 1 1 5
3 5 1 4

样例输出 #1

Y
N
Y
Y
Y

提示

本题时限 1s，内存限制 128M，因新评测机速度较为接近 NOIP 评测机速度，请注意常数问题带来的影响。

$20\%$ 的数据 $n, q\le200$。

$40\%$ 的数据 $n, q\le 2\times10^3$。

$70\%$ 的数据 $n, q\le 5\times10^4$。

$100\%$ 的数据 $1\le n, q\le10^5$。

先上结论：

如果两条路径相交，那么一定有一条路径的LCA在另一条路径上

而判断一个节点x，是否在路径s-t上需要满足如下几个条件

- 条件一：deep[x]>=deep[LCA(s,t)]

- 条件二：LCA(s,x)=x或LCA(t,x)=x;

判断条件一：（以下一大段内容可以缩写为：不妨设depth[x]>=depth[y]）

只需讨论两种情况：

假设要求算a-b和c-d两条路径是否相交，设：

x=LCA(a,b);

y=LCA(c,d);

则先比较：depth[x]和depth[y]的大小，如果depth[x]>=depth[y]不做处理，如果depth[x]<depth[y]则对应的交换x与y，a与c，b与d，

使得现在的x,a,b,这一组数有depth[x]>depth[y]

然后再判断条件二是否成立即可；

样例代码（LCA部分和DFS部分不变，主程序如下）

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin.tie(0);
    int n,q,v,u;
    cin>>n>>q;
    lg[0]=0;
    for(int i=1;i<=n;i++)
    {
        lg[i]=lg[i-1]+(1<<lg[i-1]==i);
    }
    for(int i=1;i<=n-1;i++)
    {
        cin>>u>>v;
        ipoint[u].emplace_back(v);
        ipoint[v].emplace_back(u);
    }
    dfs(1);
    int a,b,c,d;
    for(int i=1;i<=q;i++)
    {
        cin>>a>>b>>c>>d;
        int x=LCA(a,b);
        int y=LCA(c,d);
        if(depth[x]<depth[y])
        {
            swap(x,y);
            swap(a,c);
            swap(b,d);
        }
        if(LCA(c,x)==x || LCA(d,x)==x)
            printf("Y\n");
        else printf("N\n");
    }
    return 0;
}