一、引例

1、树-结点间最短距离
【例题1】给定一棵n(n <= 100000)个结点的树，以及m(m <= 100000)条询问(u, v),对于每条询问，求u和v的最短距离？

我们知道，一个普通的无向图求两点间最短距离可以采用单源最短路，将时间复杂度大致控制在O(nlogn)，但是当询问足够多的时候，这并不是一个高效的算法。从树的性质可知，树上任意两点间有且仅有一条简单路径（路径上没有重点和重边），所以树上任意两点间的最短距离其实就是这条简单路径的长度。如图一-1-1所示，要求u到v的距离，我们需要知道红色路径A(u->r），蓝色路径B(v->r)，红蓝公共路径C(a->r)，那么u->v的路径显然就可以通过A、B、C三者的长度计算出来，令dist[x]表示从x到树根r的简单路径的长度，则u到v的距离可以表示成如下：dist[u] + dist[v] – dist[a]。

那么问题来了，a是什么，我们来看a->r路径上的所有结点既是u的祖先，也是v的祖先，所以我们给它们一个定义称为公共祖先（Common Ancestors），而a作为深度最深的祖先，或者说离u和v最近的，我们称它为最近公共祖先（Lowest Common Ancestors），简称LCA。

图一-1-1

二、LCA（最近公共祖先）

1、朴素算法
于是求树上两点间的距离转化成了求两个结点的最近公共祖先问题上来了，最容易想到的办法是将u->r和v->r的两条路径通过递归生成出来，并且逆序保存，然后比较两条路径的公共前缀路径，显然公共前缀路径的尾结点就是u和v的最近公共祖先，但是这个算法在树退化成链的时候达到最坏复杂度O(n)，并不可行。

2、步进法
对于两个结点u和v，假设它们的最近公共祖先为lca(u, v)，用depth[x]表示x这个结点的深度，pre[x]表示x的父结点。那么很显然，有depth[ lca(u, v) ] <= min{depth[u], depth[v]}，通过这样一个性质，我们可以很容易得出一个算法：
1) 当depth[u] < depth[v]时，lca(u, v) = lca(u, pre[v]);
2) 当depth[u] > depth[v]时，lca(u, v) = lca(pre[u], v);
利用以上两个条件，可以将u和v不断向根进行步进，递归求解，直到u == v时，这里的u或v就是原先要求的(u, v)的最近公共祖先。

3、记忆化步进法
【例题2】如图二-3-1的网络拓扑树，给定两个客户端(x, y)，需要找到一个离他们最近的服务器来处理两个客户端的交互，客户端和服务端数量小于等于1000，但是询问数Q <= 10^8。

图二-3-1

这是一个典型的LCA问题，并且询问很多，还有一个特点是总的树结点树并不是很多，所以在步进法计算LCA的时候，可能会遇到很多重复的计算，具体是指计算lca(u, v)的时候可能在某次查询的时候已经被计算过了，那么我们可以把这个二元组预先存在数组中，即lca[u][v]，这样做可以避免多次查询中遇到的冗余计算。但同时也带来一个问题，就是空间复杂度是O(n^2)，对于n = 100000的情况下内存已经吃不消了，记忆化步进法只适用于n在千量级的情况。

4、tarjan算法
tarjan算法采用深度优先搜索递归计算结点(u, v)的LCA。具体的思想是在搜索过程中将一棵树进行分类，分类如下：
a.以结点x为根的子树作为a类结点；
b.以pre[x]为根的子树去掉a类结点，为b类结点；
c.以pre[ pre[x] ]为根的子树并且去掉a、b两类，为c类结点；依此类推…

图二-4-1

如图二-4-1所示，对这棵树进行深度优先搜索，深灰色结点（之所以不用黑色是因为线条也是黑的）表示以该结点为根的子树已经尽数访问完毕；浅灰色结点表示该结点为根的子树正在进行访问，且尚未访问完毕；白色结点表示以该结点为根的子树还没开始访问。图中红色圈出的部分为上文提到的a类结点；黄色圈出的部分为b类结点；蓝色为c类结点；绿色为d类结点，以此类推，不同的颜色属于不同的集合。所谓一图在手，胜过万语千言，从图中很容易就能看出，x和所有绿色结点的LCA都为pre[pre[pre[x]]]，即x的曾祖父结点；和所有蓝色结点的LCA都为pre[pre[x]]，即x的祖父结点；和所有黄色结点的LCA都为pre[x]，即x的父结点。

可能有人对这里集合的概念表示不理解，举个例子就能明白了，我们还是沿用上图，将图上的结点进行编号，如图二-4-2所示，可以得到其中三个集合为：
B = {8,13} C = {4,7,11,12,16} D = {1,2,3,5,6,9,10,14,15}
每个集合对应一棵子树，按照tarjan算法的思路，当给定任意一个结点，我们需要得到这个结点所在集合对应的子树的根结点，这里分两步走：
1) 找到结点对应的集合；
2）找到集合的根；

第2)步可以预先将值保存在数组中，但是集合不像数字，不能作为数组的下标。而我们注意到这里的集合都是互不相交的，这一点是非常关键的，这就意味着我们可以用一个集合中的元素来作为这个集合的“代表元”。假设B的代表元为13，C的代表元为7，D的代表元为5，用ancestor数组来存储集合的根结点，则有ancestor[13] = 8, ancestor[7] = 4, ancestor[5] = 1，于是第2)步就能在O(1)的时间内完成了。
第1)步其实可以描述成给定一个结点，求该结点所在集合的代表元。这里先不讨论实现，因为这个操作会在第三节并查集中花很长的篇幅来讲。

图二-4-2

对集合有一定了解后，让我们最后总结下这个算法究竟是如何实现的。
1) 初始化所有结点颜色colors[i] = 0，对树T进行深度优先搜索；
2) 访问到结点u时，将u单独作为一个集合，并且令ancestor[u] = u，即这个集合的根结点为u，然后跳转到3)；
3) 访问u的所有子结点v，递归执行2)，当v所在子树结点全部访问完毕后，将v所在集合和u所在集合合并（执行merge(u, v)），并且令新的集合的祖先为u（执行ancestor[find(u)] = u）；
4) 当u所在子树结点全部访问完毕后，置colors[u] = 1，枚举所有和u有关的询问：(u, v)，如果colors[v]等于1，那么记录u和v的最近公共祖先为ancestor[ find(v) ]；

这里有两个神奇的函数，merge(u, v)和find(u)，其中merge(u, v)表示合并u和v所在的两个集合，find(u)则表示找到u所在集合的代表元。如果对这个算法已经有一定的认知，那么趁热打铁，来看下伪代码是如何实现的。

注释1:创建一个集合，集合中只有一个元素u，即{ u }
注释2:因为u所在集合只有一个元素，所以也可以写成ancestor[u] = u
注释3:edge[u][0…size-1]存储的是u的直接子结点
注释4:递归计算u的所有直接子结点v
注释5:回溯的时候进行集合合并，将以v为根的子树和u所在集合进行合并
注释6:对合并完的集合设置集合对应子树的根结点，find(u)为该集合的代表元
注释7:u为根的子树访问完毕，设置结点颜色
注释8:枚举所有和u相关的询问(u, v)，如果以v为根的子树已经访问过，那么ancestor[find(v)]肯定已经计算出来，并且必定是u和v的LCA

tarjan算法的时间复杂度为O(n+q)，其中n为结点个数，q为询问对(u, v)的个数。但是在进行深搜之前首先需要知道所有的询问对，所以是一个离线算法，不能实时进行计算，局限性较大。

【例题3】在一个可视化的界面上的一棵树，选中某些结点，然后要求在文件中保存一棵最小的子树，使得这棵子树包含所有这些选中的结点。
doubly算这个是实际文件保存中比较经典的问题，我们可以选择两个结点求出LCA，然后用这个LCA再和两一个点求LCA，以此类推…n个结点经过n-1次迭代就能求出n个结点的LCA，这个LCA就是要保存的子树的根结点了。

5、doubly算法

doubly算法（倍增法）是在线算法，可以实时计算任意两点间的LCA，并且每次计算时间复杂度是O(1)的。

该算法同样也是基于深度优先搜索的，遍历的时候从根结点开始遍历，将遍历的边保存下来，对于一棵n个结点的树来说总共有n-1条边，那么遍历的时候需要保存2*(n-1)条边（自顶向下的边，以及回溯时的边，所以总共两倍的边），这些边顺序存储后相邻两条边的首尾结点必定是一致的，所以可以压缩到一个一维数组E中，数组的长度为2*(n-1)+1，然后建立一个辅助数组D，长度和E一致，记录的是E数组中对应结点的深度，这个在遍历的时候可以一并保存，然后再用一个辅助数组I[i]来保存i这个结点在E数组中第一次出现的下标。至此，初始化工作就算完毕了。

那么当询问两个结点u和v的LCA时，我们首先通过辅助数组I获取两个结点在D数组中的位置，即I[u]和I[v]，不妨设I[u] <= I[v],那么在D数组中的某个深度序列D[ I[u], I[u]+1, … I[v]-1, I[v] ]，其实表示的是从u到v的路径上每个结点的深度，而之前我们已经知道树上任意两个结点的简单路径有且仅有一条，并且路径上深度最小的点就是u和v的LCA，所以问题转化成了求D[ I[u], I[u]+1, … I[v]-1, I[v] ]的最小值，找到最小值所在下标后再到E数组索引得到结点的值就是u和v的LCA了。

图二-5-1

如图二-5-1为n = 7个结点的一棵树，其中0为根结点，6条边分别为(0,5)(5,2)(2,4)(0,3)(3,1)(3,6)。注意这里的边是有向边，即一定是父结点指向子结点，如果给定的是无向边，需要预先进行处理。如右图，从根结点进行遍历，其中红色的边为自顶向下的边，绿色的边为回溯边，回溯边一定是子结点指向父结点的，蓝色的小数字代表边的遍历顺序，即第几条边，将所有的边串起来就变成这样了：
(0,5) -> (5,2) -> (2,4) -> (4,2) -> (2,5) -> (5,0) -> (0,3) -> (3,1) -> (1,3) -> (3,6) -> (6,3) -> (3,0)

然后我们将这些边压缩到数组E中，得到：
E[1 … 2n-1] = 0 5 2 4 2 5 0 3 1 3 6 3 0

对数组E中对应的结点在树上的深度记录在数组D中，得到：
D[1 … 2n-1] = 0 1 2 3 2 1 0 1 2 1 2 1 0

再将每个结点在数组E中第一次出现的位置记录在数组I中，得到：
I[0 … n-1] = 1 9 3 8 4 2 11
注意：这里的数组E和D都是1-based，而I数组是0-based，这个是个人习惯，可自行约定，不必纠结。

根据LCA的性质，有LCA(x, y) = E[ Min_Index( D, I[x], I[y] ) ]，其中Min_Index(Array, i, j)表示Array数组中[i, j]区间内的最小值对应的下标，那么问题的难点其实就是在于求Min_Index(Array, i, j)了，这个问题就是经典的区间最值问题，最常见的可以采用线段树求解，建好树后单次查询的时间复杂度为O(logn)，当然还有一种更加高效的算法，查询复杂度可以达到严格的O(1)，这就是第四节要讨论的RMQ问题。
由于tarjan算法中还有一个有关集合操作的遗留问题尚未介绍，这里先来看史上最轻量级的数据结构——并查集。

三、并查集

1、”并”和”查”
并查集是一种处理不相交集合的数据结构，它支持两种操作：
1）合并操作merge(x, y)。即合并两个原本不相交的集合，此所谓“并”。
2）查找操作find(x)。即检索某一个元素属于哪个集合，此所谓“查”。

讲个简单的故事来加深对并查集的理解，这个故事要追溯到北宋年间。话说北宋时期，朝纲败坏，奸臣当道，名不聊生。又有外侮辽军大举南下，于是众多能人异士群起而反，各大武林门派同仇敌忾，共抗辽贼，为首的自然是中原武林第一大帮-丐帮，其帮主乃万军丛中取上将首级犹如探囊取物、泰山崩于前而面不改色的北乔峰；与其齐名的空有一腔抱负、壮志未酬的南慕容带领的慕容世家；当然也少不了天下武功的鼻祖-少林，以及一些小帮派，如逍遥派、灵鹫宫、无量剑、神农教等等。我们将每个门派（帮派）作为一个集合，从中选出一个代表作为这个集合的标识，姑且认为门派（帮派）的掌门（帮主）就是这个代表。
作者有幸成了“抗辽联盟”的统计员，统计员只有一个工作，就是接收一条条同门数据，然后统计共有多少个门派，好进行分派部署。同门数据的格式为(x, y)，表示x和y属于同一个门派，接收到一条数据，需要对x所在的群体和y的群体进行合并，当统计完所有数据后有多少个集合就代表多少个门派。

这个问题其实隐含了两个操作：1、查找a和b是否已经在同一个门派；2、如果两个人的门派不一致，则合并这两个人所在集合的两堆人。分别对应了并查集的查找和合并操作。
如图三-1-1所示，分别表示丐帮、少林、逍遥、大理段氏四个集合。

图三-1-1

2、朴素算法
接下来来讨论下并查集的朴素实现，既然是朴素实现，当然是越朴素越好。朴素的只需要一个数组就能表示集合，我们用set[i]表示i所在的集合，这样查找操作的时间复杂度就能通过下标索引达到O(1)（可以把set数组理解成哈希表）；合并x和y的操作需要判断set[x]和set[y]是否相等，如果不相等，需要将所有满足set[i]等于set[x]的set[i]变成set[y]，由于这里需要遍历set[i]，所以时间复杂度为O(n)。图三-2-1展示了朴素算法的一个例子，该数组一共记录了四个集合，并且用每个集合的最小数字作为该集合的标识。

图三-2-1

给出朴素算法的伪代码如下：

初始化set[i] = i,每次得到一组数据(x, y),就执行merge(x, y)，统计完所有数据后，对set数组进行一次线扫，就能统计出总共有多少个门派。

3、森林实现
由于朴素实现合并操作的时间复杂度太高，在人数很多的情况下，效率上非常吃亏，如果有n次合并操作，那么总的时间复杂度就是O(n^2)。所以我们将集合的表示进行一定的优化，将一个个集合用树的形式来组织，多个集合就组成了一个森林。用pre[i]表示i在集合树上的父结点，当pre[i]等于i时，则表示i为这棵集合树的根结点。那么显而易见的，对于合并操作(x, y)，只需要查找x和y在各自集合树的根结点rx和ry，如果rx和ry不相等，则将rx设为ry的父结点，即令pre[ry] = rx。查找操作更加简单，只要顺着父结点一直找到根结点，就找到了该结点所在的集合。初始化pre[i] = i，即表示森林中有n棵一个结点的树。如图三-3-1为合并x,y所在集合的操作。

图三-3-1

给出森林实现的伪代码如下：