LCA

缘起

LCA问题，即最近公共祖先问题（lowest common ancestor）. 问题描述如下

1
对于一棵有根树T（不一定是二叉树哦）的任意两个节点u，v，求出LCA(T, u, v)，即离根节点root最远的节点x，使得x同时是u和v的祖先。

LCA问题其实非常有用. 你们在做WEB开发的时候用的各种树的插件（如jquery、ztree等），要快速确定两个节点的LCA才能进行绘图.

分析

其实LCA问题有一种很明显的暴力算法——你不是要求i和j两个节点的LCA嘛（例如上图的9和12）？ 那么我们只需要i和j不断的向根节点找，则得到两个奔向根节点的数组. 则只需要找到这两个数组索引最小的公共数字即可. 例如求解 LCA(9,12), 则

9的数组是9–>6–>3–>1, 而 12的数组是 12–>10–>7–>3–>1 那么公共的索引最小的数字就是3，所以LCA(9,12)=3, 但是这样的话，解决每次LCA询问的复杂度是最坏O(n)（树蜕化为链表），这有时是不可接受的. 事实上，LCA的解法有如下两种.

  1. 在线算法（online）， 基于欧拉环游转换为RMQ问题. 其中RMQ问题使用ST算法.

    ps: 所谓欧拉环游指的是遍历图中所有边一次并且回到出发点,注意，点未必只经过一次（这里将树看成是无向图）.这里比哥尼斯堡七桥问题要严格，哥尼斯堡七桥问题不要求回到出发点.

    本算法的想法可以使用下图表述

    首先按照上图中的箭头（即把树的弧看做无向图的边）进行欧拉环游. 记录此次环游的时间戳, 这需要一个数组e. 然后记录此次环游每个时间戳到达的树的深度. 这又需要一个数组d. 最后需要记录每个节点（如上面的9、12）最早出现的时间戳. 这又需要一个数组 f, 也就是说本算法需要总共3个数组. 最后我们就知道

    1
    LCA(i,j) = RMQ(d, f[i], f[j])，其中RMQ是求极小,i,j是树上的节点, 例如9和12, 其实想想是对的,这里假设f[i]<f[j]（不满足的话，可以交换调整）, 因为f[i]保证了i的孩子都参与其中, f[j]保证了j的孩子（肯定不会是LCA啦）不会参与其中. 所以求出的就是从i到j深度最小的节点在d中的索引，也就是时间戳，则可以拿着这个时间戳到e中去求取最后的LCA结果.

    即将树的LCA问题转换为了欧拉环游之后的深度数组d的RMQ极小问题.

  2. 离线算法（offline），是tarjan算法. 这个我后面会再写文章.

下面给出LCA问题的 欧拉环游（其实就是一个dfs）转换为RMQ解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include "stdafx.h"
#include <stdio.h>
#include <vector>
#define LOCAL

using namespace std;

const int MAX_N = 20, INF=0x3f3f3f3f; // 树最多20个节点
vector<int> tree[MAX_N]; // 树（使用孩子链表法表示树，注意，LCA问题中，这棵树未必是二叉树）0索引不用
int e[MAX_N<<1], d[MAX_N<<1], f[MAX_N],n, root, indeg[MAX_N],x, st[MAX_N<<2][MAX_N<<2]; // 因为是欧拉环游，所以每个节点会被访问2次, 所以涉及时间戳的e和d的容量要乘以2, 但是f不需要. 因为f是每个点的最早时间戳，0索引都不用(除了st的第一个索引), n是树的顶点的个数,indeg是入度域, 仅仅用于求根节点,x是时间戳
// 注意，为什么这里st会是乘以4? 因为这里的st是d的st表
typedef vector<int>::iterator it;

void init()
{
	scanf("%d", &n);
	for (int i = 0,j,k;i<n-1;i++) // n个顶点的树，必定n-1条边，所以e[1,...,2n-1],d[1,...,2n-1],f[1,..,n]（看看文章中的图就知道了）
	{
		scanf("%d%d", &j, &k); // 输入的弧是 j-->k
		tree[j].push_back(k); // 注意，这里不能再写 tree[k].push_back(j), 不然下面的dfs就会死循环——想想1到了2，2又回到了1，然后1又回到了2....
		indeg[k]++;
	}
	for (int i =1 ;i<=n;i++)
	{
		if (!indeg[i])
		{
			root = i;
			break;
		}
	} 
}

void dfs(int i, int depth) // 欧拉环游, i是当前节点, depth是当前树的深度
{
	e[++x] = i,d[x] = depth,f[i] = x; // 记录当前时间戳(x)发生的事情
	for (it p = tree[i].begin(); p!=tree[i].end(); p++) // 递归子节点
	{
		dfs(*p, depth+1);
		e[++x] = i; // 注意，因为是欧拉环游，所以要回来的.即要再次进入的.就像文章中说的那样, 欧拉环游每个节点进入e的次数未必是1次,但是边的遍历次数都是1次
		d[x] = depth; // 但是 f[i]不再改变了
	}
}

void build() // 构建d的st表，但是注意, 此时st中存储的不再是最小值，而是最小值对应的索引, 因为我们的rmq需要的是索引
{
	for (int i = 1;i<=(n<<1)-1;i++) st[0][i] = i;
	int k = 1;
	while((1<<k)<((n<<1)-1)) // 构建st表的第k层
	{ // 注意，这里没有引入INF，否则 d[INF] 越界了, 反而麻烦
		for (int i = 1; i<=(n<<1)-1; i++)st[k][i] = i+(1<<(k-1))>=(n<<1)? st[k-1][i]:d[st[k-1][i]]<d[st[k-1][i+(1<<(k-1))]]?st[k-1][i]:st[k-1][i+(1<<(k-1))];
		k++;
	}
}

int rmq(int i, int j) // 找d[i,..,j]上的最小值对应的索引（即时间戳）
{
	int k = 0;
	while((1<<k)<=j-i+1)k++;
	return d[st[k-1][i]]<d[st[k-1][j-(1<<(k-1))+1]]?st[k-1][i]:st[k-1][j-(1<<(k-1))+1];
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in","r",stdin);
#endif
	init(); //初始化树(包括树的结构和根节点)
	dfs(root,0); // 从根节点开始, 规定根节点位于的树的深度是0
	build(); // 构建st表
	int i,j;
	while(~scanf("%d%d", &i, &j))
	{
		int x = f[i],y = f[j];
		if (x>y) swap(x,y); // 保证 x<=y
		printf("%d\n", e[rmq(x,y)]);
	}
	return 0;
}
/*
测试数据
13
6 8
6 9
7 11
10 13
7 10
3 5
1 2
1 4
3 7
1 3
10 12
3 6
9 12
5 11
12 11
*/

本算法的复杂度是 O(nlogn)~O(1). 事实上，LCA问题还可以使用笛卡尔树进行优化，成为O(N)~O(1)的算法，这个我后面会继续写文章论述.