Question

Tree

“树”。树是一种很特别的图。树的定义是：任两点之间都相通，并且没有“环”的图。“ 环 ”是指绕圈子的循环路线。

树的定义对初学者来说或许太过抽象。换个说法吧：一棵树可想做是由一个点开始，藉由许多条边不断地延伸拓展到其他点，而且点和边都不会重複地被拓展到。

Node

“节点”。进行延伸拓展的点、被延伸拓展到的点，称作“节点”，也就是说树上的点都是“节点”。

【注：为了方便，以下仍称呼“点”。】

Branch

“枝”。延伸拓展所用到的边称作“枝”，也就是说树上的边都是“枝”。一个点藉由边往外延伸拓展，称作“分枝 Branching”。

【注：为了方便，以下仍称呼“边”。】

Root

“根”。方才提到，一棵树可想做是由一个点开始分枝──这个点便是“根”。一棵树上的每一个点都可以作为根。

Leaf

“叶”。在一棵树上选定根后，由根开始不断分枝，途中所有无法继续分枝的点皆是“叶”。

也可以不选定根，这种情况下，只连著一条边的点都是“叶”。

如果树上总共只有一个点，那麽此点既是根、也是叶。

Level

“层”。在一棵树上选定根后，按照拓展的顺序（也就是按照每个点离根的距离），可以将树上的点分层次，使得树上每一个点都拥有一个层数。如果改变根，那麽分层的结果就会不同。

还有另一种比较少见的分层方式，是设定所有叶在同一层，由叶开始计算层数。

Parent & Child

“父亲”与“小孩”。在一棵树上选定根后，以边相连的任两点，靠近树根者相对地称作“父亲”，靠近树叶者相对地称作“小孩”。

一个点的父亲，是指与其相邻的点当中，较此点靠近树根者，为其父亲。父亲只会有一个，特例是：树根没有父亲。

一个点的小孩，是指与其相邻的点当中，较此点靠近树叶者，为其小孩。小孩可以是任意多个，特例是：树叶没有小孩。

Ancestor & Descendant

“祖先”与“子孙”。在一棵树上选定根后，一个点的父亲、父亲的父亲、……皆是此点的“祖先”。一个点的小孩、小孩的小孩、……皆是此点的“子孙”。

Directed Tree

在一棵树上选定树根后，可以把边的方向设定成分枝的方向、远离树根的方向；也可以把边的方向设定成朝向树根的方向，但是这种情况比较少。

Weight

一棵树可以有权重。当边拥有权重时，一棵树的权重等于树上所有边的权重总和。

Forest

“森林”。很多棵树称作一丛“森林”。只有一棵树也是“森林”。

树的特性

1. 树没有环。
2. 树上所有点之间都相连通。
3. 没有环的图，就是树或森林。
   没有环的图、连通的图，就是树。
4. 任意两点之间只有唯一一条路径。
5. 在树上任意添加一条边，就会产生环。
6. 在树上任意删除一条边，一颗树就裂成两棵树。
7. 边数等于点数减一。

UVa 615 599

Tree 资料结构

树是一种图。图的资料结构 adjacency matrix、adjacency lists 可以储存一棵树。值得一提的是，一棵树刚好 V 个点、V-1 条边，所以 adjacency lists 的空间複杂度是 O(V+E) = O(V)。

顺便一提。有根树（森林），例如 DFS Forest、BFS Forest，可以只用一条阵列储存每个点的父亲。

Tree Property

先看个图片

图片中省略了点的编号。

parent-child relationship

建立 DFS tree 或者 BFS tree，就可以轻鬆判断一点是不是另一点的父亲。

ancestor-descendant relationship

利用 DFS 的遍历顺序，就可以轻鬆判断一点是不是另一点的祖先。

distance

一棵树、两点之间的“距离”，就是两点之间的边数。

由其中一个点开始进行 BFS 或 DFS 即可。

UVa 1599

depth

一棵有根树、每个点的“深度”，就是根到每个点的距离。

由根开始进行 BFS 或 DFS 即可。

Kth Ancestor

Kth Ancestor（Level Ancestor）

一棵有根树，树上一个点的祖先，通常有许多个。

现在要找到上 k 辈祖先。往树根走 k 步。

演算法（Preprocessing）

建立表格，纪录每一点的祖先。很容易想到两种策略：

每个节点做为起点，实施遍历，找到所有子孙。

每个节点做为起点，走向树根，找到所有祖先。

建立需时 O(V^2)，查询需时 O(1)。

演算法（Jump Pointer Algorithm）

http://tmtacm.blogspot.tw/2016/01/blog-post_15.html

预先算好每个节点的上一辈祖先、上两辈祖先、上四辈祖先、上八辈祖先、……，再以二分搜寻找到上 k 辈祖先。

辈分太高，超出树根时，可将祖先直接设定成树根，比较容易实作程式码。

建立需时 O(VlogV)，查询需时 O(logV)。

演算法（Ladder Algorithm）

http://tmtacm.blogspot.tw/2016/01/blog-post_15.html

一棵树分解为数条不重叠路径：从树根走到最深的树叶，形成一条路径，然后递迴分解其馀子树。

预先算好树上每一点隶属于哪一条路径。预先算好每条路径起点的上一辈祖先、上两辈祖先、上三辈祖先、……、上高度辈祖先，再以倍增搜寻找到上 k 辈祖先。

建立需时 O(VlogV)，查询需时 O(logV)。

演算法（Jump Pointer Algorithm + Ladder Algorithm）

一、找到祖先，辈分是 2 的次方、略小于 k。（若 2 的次方恰等于 k，则演算法结束）。

二、辈分再翻倍，显然超过 k。该祖先高度再翻倍，显然超过 k。该祖先所在路径保证最深最高，保证其祖先表格含有上 k 辈祖先。

建立需时 O(VlogV)，查询需时 O(1)。

演算法（Micro Tree）

Micro Tree 没有实务上的价值，只有理论上的价值。

建立需时 O(V)，查询需时 O(1)。

演算法（Euler Tour Technique）

https://en.wikipedia.org/wiki/Level_ancestor_problem

建立需时 O(V)，查询需时 O(1)。

Lowest Common Ancestor

Lowest Common Ancestor

一棵有根树，树上两点的共同祖先当中，离根最远、深度最深的那一个共同祖先，称作“最低共同祖先”，常简称为 LCA。

演算法（Preprocessing）

建立表格，纪录所有点对的 LCA。

知道 x 与 y 的 LCA，也就知道 x 的小孩与 y 的小孩的 LCA 了。递迴公式如下：

LCA(x, y) =
 { x                   , if x = y
 { x                   , if x = parent(y)
 { y                   , if y = parent(x)
 { LCA(parent(x), y)   , otherwise
 { LCA(x, parent(y))   , otherwise

LCA(x, y) =
 { x                   , if x = y or x = parent(y)
 { LCA(parent(x), y)   , otherwise

建立需时 O(V^2)，查询需时 O(1)。

UVa 12182

演算法（Tarjan's Algorithm）

用来求出所有点对的 LCA。亦得求出部分点对的 LCA，必须预先知道是哪些点对，排好顺序以利实作。

运用 DFS 遍历顺序，配合 Disjoint-sets Forest，把已经拜访过的点，依照层级聚合起来，方便找到 LCA。

时间複杂度分成三部份讨论：

一、DFS：端看树的资料结构。使用 adjacency matrix，时间複杂度是 O(V^2)；使用 adjacency lists，时间複杂度是 O(V+E)。

二、union：直接考虑 p[]的存取次数，总共是 O(V)。

三、find：求出所有点对的 LCA，每次 find 最多存取两次 p[]，总共是 O(V^2)。求出部分点对的 LCA，p[]的存取次数只降不升，最多是 O(V^2)，最少是 O(1)。

总时间複杂度是 O(V^2)。

宏观来看，合併连成一线、没有分枝的边，以树根作为起点的单源最短路径们的长度总和，就是 p[]的存取次数上限。

UVa 12238 ICPC 2045

演算法（Jump Pointer Algorithm）

预先算好每个节点的上一辈祖先、上两辈祖先、上四辈祖先、上八辈祖先、……，再以二分搜寻找到 LCA。

辈分太高，超出树根时，可将祖先直接设定成树根，比较容易实作程式码。

建立需时 O(VlogV)，查询需时 O(logV)。

ICPC 5061

演算法（Heavy-Light Decomposition）

建立需时 O(V)，查询需时 O(logV)。

请见本站文件“ Heavy-Light Decomposition ”。

演算法（Euler Tour Technique）

建立需时 O(V)，查询需时 O(logV)。

请见本站文件“ Euler Tour Technique ”。

亦得利用“ Cartesian Tree ”将 LCA 问题转换成±1RMQ 问题。建立需时 O(V)，查询需时 O(1)。