一、 LCA问题的简介

LCA问题（Least Common Ancestors，最近公共祖先问题），是指给定一棵有根树T，给出若干个查询LCA(u, v)（通常查询数量较大），每次求树T中两个顶点x和y的最近公共祖先。

询问：LCA(x, y)，即求x与y的最近公共祖先。

题目描述：通常是先给定一棵有根树，然后询问（两种询问方式，下文会提及）。

二、LCA题目的分类

在线算法：你问我一次，我立马回答你。

离线算法：等你问完了，我再一次性回答你。

三、LCA问题的解法

图1

以下以图1为例，分别对两个分类的算法作相应的讲解：

1. 离线算法——Tarjan(后序DFS+并查集)

【算法步骤】

a. 后序遍历访问树（假设现在访问到结点x并且x不是叶子）

b. 将以x为根的子树合并到一个集合中（集合中有共同的特性数值，我称之为ancestor，即x）

c. 然后检查是否有与x有关的查询，假设有并且x对应的y已经访问过，则得到答案（答案为y的ancestor）

应该注意的是，得到答案的顺序和查询的顺序不一样，需要另行处理。

【举例说明】查询LCA(4, 7)， LCA(5，7)：

a.访问完4之后{4}与{1}合并为{4，1}，则ancestor{1,4}= 1。

b.访问7，先遍历与7有关的查询，发现有关于7和4的查询，并且4在前面已经c.访问过了，于是得到LCA(4,7) = ancestor{1,4} = 1。

c.访问完7后{7}与{5}合并为{7，5}，则ancestor{5,7}=5。

d.此时访问5，遍历与5有关的查询，发现有关于5和7的查询，并且7在先前已经访问过，则LCA(5,7)= ancestor{5,7} = 5;

e.此时该访问1了，将{4,1}与{5,7}合并为{4,1,5,7}，则ancestor{4,1,5,7} = 1。

【代码实现】

初始输入树g、查询que

vector<int> g[N];//邻接表存储树
vector<int> que[N];//存储查询
int root;//树根
int indeg[N];//入度用于求树根
void inputtree()//树的存储
{
    cin>>n;
    //初始化
    for(int i = 0; i < n; i++)
    {
        g[i].clear();
        indeg[i] = 0;
    }
    //根据有向边存储树
    for(int i = 0; i < n-1; i++)
    {
        int x, y;
        cin>>x>>y;
        g[x].push_back(y);
        indeg[y]++;
    }
    //求根
    for(int i = 0; i < n; i++)
        if(!indeg[i])   {root = i; break;}
}
void inputque()//输入询问
{
    //初始化
    for(int i = 0; i < n; i++)
        que[i].clear();
    cin>>m;
    //保存问题
    for(int i = 0; i < m; i++)
    {
        int u, v;
        cin>>u>>v;
        que[u].push_back(v);
        que[v].push_back(u);
    }
}

并查集部分（集合的操作）

int fa[N];
void initset()//初始化集合
{
    for(int i = 0; i < n; i++)
        fa[i] = i;
}
int findx(int x)
{
    if(fa[x] == x)  return x;
    return fa[x] = findx(fa[x]);
}
void unionx(int nx, int ny)//合并集合
{
    int x = findx(nx);
    int y = findx(ny);
    if(x != y)  fa[y] = x;
}

Tarjan部分（代码为【算法步骤】）

bool vis[N];//该结点是否访问过
int ancestor[N];//已访问节点集合的祖先
void Tarjan(int x)
{
    for(int i = 0; i < g[x].size(); i++)
    {
        Tarjan(g[x][i]);//后序遍历
        unionx(x, g[x][i]);//子树与根节点合并
        ancestor[findx(x)] = x;//合并后集合的祖先
    }
    vis[x] = 1;
    for(int i = 0; i < que[x].size(); i++)
        if(vis[que[x][i]])
            printf("%d与%d的LCA为:%d\n", x, que[x][i],
                   ancestor[findx(que[x][i])]);//输出答案的顺序与查询的顺序不一致
}

【相关入门题】：hdu2586

2. 在线算法——基于RMQ（先序DFS+ST算法）

【算法步骤】

a. 先序遍历树，得出欧拉序列f、各结点深度序列depth和各结点在f中第一次出现的位置序列pos。

b. 当有一个查询LCA(x，y)时，在f(x，y)中利用RMQ找到depth值最小的z，则z为LCA(x，y)。

【举例说明】查询LCA(4, 7)：

a. 先序遍历树得出有序的 f和depth序列：

f{0->1->4->1->5->7->5->1->0->2->0->3->6->3->0}

depth{0->1->2->1->2->3->2->1->0->1->0->1->2->1->0}

pos{0(0),1(1),9(2),11(3),2(4),4(5),12(6),5(7)}为方便理解，()内为结点。

b. 查询LCA(4,7)，利用RMQ求出pos(4)与pos(7)之间depth{2->1->2->3}值最小的1，其对应的结点为1，即LCA(4，7) = 1。

【代码实现】

初始化输入树g

int root;//树根
int indeg[N];//结点的入度
void input()
{
    for(int i = 0; i < N-1; i++)
    {
        int u, v;
        cin>>u>>v;
        g[u].push_back(v);
        indeg[v]++;
    }
    for(int i = 0; i < N; i++)
        if(!indeg[i])   {root = i;break;}
}

DFS部分求得序列f、depth、pos

int f[2*N+1];//欧拉序列
int depth[2*N+1];//x的深度序列
int cnt;//初始化为0
int pos[N];//x第一次出现的位置,初始化为-1
void dfs(int x, int d)
{
    pos[x] = cnt;
    depth[cnt] = d;
    f[cnt++] = x;
    for(int i = 0; i < g[x].size(); i++)
    {

        dfs(g[x][i], d+1);
        depth[cnt] = d;//对分支结点的处理
        f[cnt++] = x;
    }
}

RMQ

int dp[N][N];//最小值对应的下标
void init_RMQ()
{
    for(int i = 0; i < N; i++)
        dp[i][0] = i;//自己到自己的最小值下标，为自己
}
void RMQ()
{
    init_RMQ();
    for(int j = 1; j < 20; j++)
        for(int i = 0; i < N; i++)
            if(i+(1<<j)-1 < N)
                dp[i][j] = depth[dp[i][j-1]] < depth[dp[i+(1<<(j-1))][j-1]] ? dp[i][j-1] : dp[i+(1<<(j-1))][j-1];
}
int ask(int l, int r)
{
    if(l > r)   swap(l, r);
    int k = log(r-l+1.0)/log(2.0);
    return depth[dp[l][k]] < depth[dp[r-(1<<k)+1][k]] ? dp[l][k] : dp[r-(1<<k)+1][k];
}