Lca相关算法

简介

在图论和计算机科学中，最近公共祖先是指在一个树或者有向无环图中同时拥有v和w作为后代的最深的节点。在这里，我们定义一个节点也是其自己的后代，因此如果v是w的后代，那么w就是v和w的最近公共祖先。

最近公共祖先是两个节点所有公共祖先中离根节点最远的，计算最近公共祖先和根节点的长度往往是有用的。比如为了计算树中两个节点v和w之间的距离，可以使用以下方法：分别计算由v到根节点和w到根节点的距离，两者之和减去最近公共祖先到根节点的距离的两倍即可得到v到w的距离。

求解方法

在线算法ST表

在线算法和离线算法：
在计算机科学中，一个在线算法是指它可以以序列化的方式一个个的处理输入，也就是说在开始时并不需要已经知道所有的输入。相对的，对于一个离线算法，在开始时就需要知道问题的所有输入数据，而且在解决一个问题后就要立即输出结果。例如，选择排序在排序前就需要知道所有待排序元素，然而插入排序就不必。
首先咱们对于以下一棵树

分析如下

在转化成区间之后，我们可以使用RMQ相关算法来解决该问题。
对于dfs算法：

int tot,head[N],ver[2*N],R[2*N],first[N],dir[N];
//ver:节点编号 R：深度 first：点编号第一次位置 dir：距离
void dfs(int u ,int dep)
{
       vis[u] = true;
    ver[++tot] = u;
    first[u] = tot;
    R[tot] = dep;
    for(int k=head[u]; k!=-1; k=e[k].next)
        if( !vis[e[k].v] )
        {
            int v = e[k].v , w = e[k].w;
            dir[v] = dir[u] + w;
            dfs(v,dep+1);
            //下面两句表示dfs的时候还要回溯到上面
            ver[++tot] = u;
            R[tot] = dep;
        }
}

假设我们需要得到D和F的LCA，
那么我们找D和F在序列中的位置可以通过first数组发现在数组下标为3—–6,在该区间中找到深度为2，该点的编号为4，即为B点（得出区间后，我们使用RMQ维护）

void ST(int n)
{
    for(int i=1;i<=n;i++)
        dp[i][0] = i;
    for(int j=1;(1<<j)<=n;j++)
    {
        for(int i=1;i+(1<<j)-1<=n;i++)
        {
            int a = dp[i][j-1] , b = dp[i+(1<<(j-1))][j-1];
            dp[i][j] = R[a]<R[b]?a:b;
        }
    }
}
//中间部分是交叉的。
int RMQ(int l,int r)
{
    int k=0;
    while((1<<(k+1))<=r-l+1)
        k++;
    int a = dp[l][k], b = dp[r-(1<<k)+1][k]; //保存的是编号
    return R[a]<R[b]?a:b;
}

int LCA(int u ,int v)
{
    int x = first[u] , y = first[v];
    if(x > y) swap(x,y);
    int res = RMQ(x,y);
    return ver[res];
}

Tarjan离线算法

tarjan算法的有点在于相对稳定，时间复杂度也比较居中，比较容易理解
基本思路是：

1.任选一个点为根节点，从根节点开始。
2.遍历该点u所有子节点v，并标记这些子节点v已被访问过。
3.若是v还有子节点，返回2，否则下一步。
4.合并v到u上。
5.寻找与当前点u有询问关系的点v。
6.若是v已经被访问过了，则可以确认u和v的最近公共祖先为v被合并到的父亲节点a。
伪代码如下：

Tarjan(u)//marge和find为并查集合并函数和查找函数
{
    for each(u,v)    //访问所有u子节点v
    {
        Tarjan(v);        //继续往下遍历
        marge(u,v);    //合并v到u上
        标记v被访问过;
    }
    for each(u,e)    //访问所有和u有询问关系的e
    {
        如果e被访问过;
        u,e的最近公共祖先为find(e);
    }
}

完整代码：

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 1001;
vector<int> tree[MAXN];
int indegree[MAXN], ancestor[MAXN];
int nvertex, root;
int father[MAXN], rnk[MAXN];
bool visited[MAXN];
int nquery;
vector<int> query[MAXN];

void init()
{
    for(int i=0; i<nvertex; ++i){
        tree[i].clear();
        indegree[i] = 0;
        ancestor[i] = i;
        father[i] = i;
        rnk[i] = 0;
        visited[i] = false;
        query[i].clear();
    }
}

/*
int find(int x)
{
 int rt = x;
    while(rt != father[rt])
        rt = father[rt];

    while(father[x] != rt){
        int y = father[x];
        father[x] = rt;
        x = y;
    }

    return rt;
}
*/


int find(int x)
{
    if(x != father[x])
        father[x] = find(father[x]);
    return father[x];
}


void unin(int x, int y)
{
    x = find(x), y = find(y);
    if(x == y)  return ;
    if(rnk[x] > rnk[y]) father[y] = x;
 else father[x] = y, rnk[y] += rnk[x] == rnk[y];
}

void tarjan(int x)
{
    for(int i=0; i<tree[x].size(); ++i){
        tarjan(tree[x][i]);
        unin(x, tree[x][i]);
        ancestor[find(x)] = x;
    }

    visited[x] = true;

    for(int i=0; i<query[x].size(); ++i){
        if(visited[query[x][i]])
            printf("the LCA for %d and %d is %d\n", x, query[x][i], ancestor[find(query[x][i])]);
    }
}

int main()
{
    scanf("%d", &nvertex);
    init();

    int x, y;
    for(int i=1; i<nvertex; ++i){
        scanf("%d%d", &x, &y);
        tree[x].push_back(y); //x->y
        indegree[y]++;
 }

    scanf("%d", &nquery);
    for(int i=0; i<nquery; ++i){
        scanf("%d%d", &x, &y);
        query[x].push_back(y);
        query[y].push_back(x);
    }

    for(int i=0; i<nvertex; ++i)
        if(indegree[i] == 0) { root = i; break; }

    tarjan(root);

    return 0;
}

---

1. Lca介绍https://zh.wikipedia.org/wiki/%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88_(%E5%9B%BE%E8%AE%BA)
2. 在线算法ST表https://blog.csdn.net/liangzhaoyang1/article/details/52549822
3. Tarjan算法https://www.cnblogs.com/JVxie/p/4854719.html
4. Tarjan算法实现https://blog.csdn.net/freeelinux/article/details/54974044