Tree

「樹」。樹是一種很特別的圖。樹的定義是：任兩點之間都相通，並且沒有環的圖。

樹的定義對初學者來說或許太過抽象。換個說法吧：一棵樹可想做是由一個點開始，藉由許多條邊不斷地延伸拓展到其他點，而且點和邊都不會重複地被拓展到。

Node

「節點」。進行延伸拓展的點、被延伸拓展到的點，稱作「節點」，也就是說樹上的點都是「節點」。

【註：為了方便，以下仍稱呼「點」。】

Branch

「枝」。延伸拓展所用到的邊稱作「枝」，也就是說樹上的邊都是「枝」。一個點藉由邊往外延伸拓展，稱做「分枝（Branching）」。

【註：為了方便，以下仍稱呼「邊」。】

Root

「根」。方才提到，一棵樹可想做是由一個點開始分枝──這個點便是「根」。一棵樹上的每一個點都可以做為根。

Leaf

「葉」。在一棵樹上選定根後，由根開始不斷分枝，途中所有無法繼續分枝的點皆是「葉」。

另一種說法是：除了根以外，只連著一條邊的點就是葉。但這種說法有個例外：如果樹上總共只有一個點，那麼此點既是根、也是葉。

Level

「層」。在一棵樹上選定根後，按照拓展的順序（也就是按照每個點離根的距離），可以將樹上的點分層次，使得樹上每一個點都擁有一個層數。如果改變根，那麼分層的結果就會不同。

還有另一種比較少見的分層方式，是設定所有葉在同一層，並由葉開始計算層數。

Parent & Child

「父親」與「小孩」。在一棵樹上選定根後，以邊相連的任兩點，靠近樹根者相對地稱作「父親」，靠近樹葉者相對地稱作「小孩」。

一個點的父親，是指與其相鄰的點當中，較此點靠近樹根者，為其父親。父親只會有一個，特例是：樹根沒有父親。

一個點的小孩，是指與其相鄰的點當中，較此點靠近樹葉者，為其小孩。小孩可以是任意多個，特例是：樹葉沒有小孩。

Ancestor & Descendant

「祖先」與「子孫」。在一棵樹上選定根後，一個點的父親、父親的父親、……皆是此點的「祖先」。一個點的小孩、小孩的小孩、……皆是此點的「子孫」。

Directed Tree

在一棵樹上選定樹根後，可以把邊的方向設定成分枝的方向、遠離樹根的方向；也可以把邊的方向設定成朝向樹根的方向，但是這種情況比較少。

Weight

一棵樹可以有權重。當邊擁有權重時，一棵樹的權重等於樹上所有邊的權重總和。

Forest

「森林」。很多棵樹稱作一叢「森林」。

使用圖的資料結構

可以直接使用圖的資料結構來儲存一棵樹，adjacency matrix或adjacency lists都可以。

有根樹：單向（往樹根方向）

開一條int陣列，每個格子對應圖上的各個點，格子裡儲存著該點的父親。

查詢路徑時，只能往根的方向行走，無法往葉的方向行走。儘管不太便利，但是足以應付大部分情況了。【待補文字】

有根樹、無根樹：雙向

【待補文字】

UVa 10729

樹的特性

1. 樹沒有環。
2. 任意兩點之間只有唯一一條路徑。
3. 樹上所有點之間都相連通。
4. 在樹上任意添加一條邊，就會產生環。
5. 在樹上任意刪除一條邊，一顆樹就裂成兩棵樹。
6. 邊數等於點數減一。

UVa 615 599

height (rooted tree)

運用Divide and Conquer，移除一棵樹的樹根，形成許多子樹，並分頭處理子樹。

寫成程式碼之後，D&C的運作順序，剛好就是DFS的遍歷順序。因此，有人把這樣的程式碼，直接稱為DFS。這用詞並非精準，然而其過程恰是遍歷一張圖，讀取資訊算出答案，故稱之為DFS倒也無妨。

bool adj[9][9]; int DFS(int x, int px) // px是x的父親 { int h = 0; // 紀錄最高的高度 for (int y=0; y<9; ++y) if (adj[x][y] && y != px) h = max(h, DFS(y, x) + 1); return h; } void tree_height(int root) { cout << "樹的高度是" << DFS(root, root); }

diameter

樹上相離最遠的兩個點的路徑長度，便是樹的直徑。稍微修改一下計算高度的程式碼，就可以順便計算直徑。

bool adj[9][9]; int diameter = 0; int DFS(int x, int px) // px是x的父親 { int h1 = 0, h2 = 0; // 紀錄最高與次高的高度 for (int y=0; y<9; ++y) if (adj[x][y] && y != px) { int h = DFS(y, x) + 1; if (h > h1) h2 = h1, h1 = h; else if (h > h2) h2 = h; } diameter = max(diameter, h1 + h2); return h1; } void tree_diameter() { diameter = 0; // 初始化 int root = 0; // 隨便選一個樹根 DFS(root, root); cout << "樹的直徑是" << diameter; } int adj[9][9]; // 改這裡 int diameter = 0; int DFS(int x, int px) { int h1 = 0, h2 = 0; for (int y=0; y<9; ++y) if (adj[x][y] != 1e9 && y != px) // 改這裡 { int h = DFS(y, x) + adj[x][y]; // 改這裡 if (h > h1) h2 = h1, h1 = h; else if (h > h2) h2 = h; } diameter = max(diameter, h1 + h2); return h1; }

一棵樹的各種直徑一定會相交在同一點（同一群點）。

1.
反證法。
現在有兩條分開的直徑，
可是一棵樹上各點都得連通，
所以這兩條分開的直徑，中間一定有某處互相連接，
一旦連接起來，勢必變成更長的直徑，矛盾。
故所有直徑必相交。

2.
反證法。
現在已有兩條直徑相交在某一點，
如果另外一條直徑與這兩條直徑相交在另一點，
勢必變成更長的直徑，矛盾。
故所有直徑必相交在同一點（同一群點）。

UVa 10308 11695

balanced height

想辦法選定一個樹根，讓樹的高度最小。演算法請自行參考程式碼，時間複雜度為兩次DFS的時間。

bool adj[9][9]; // adjacency matrix，儲存一棵樹。 int p[9]; // DFS tree int h1[9], h2[9]; // 紀錄最高與次高的高度 int c1[9], c2[9]; // 紀錄最高與次高的來源 void record(int x, int height, int child) { if (height > h1[x]) { h2[x] = h1[x]; c2[x] = c1[x]; h1[x] = height; c1[x] = child; } else if (height > h2[x]) { h2[x] = height; c2[x] = child; } } void DFS1(int x) { h1[x] = h2[x] = 0; for (int y=0; y<9; ++y) if (adj[x][y]) if (y != p[x]) { p[y] = x; DFS1(y); record(x, h1[y] + 1, y); } else ; // 由父親過來的高度，只能留待下一波解決。 } void DFS2(int x) { if (p[x] != x) // 樹根沒有父親，不必算。 { int y = p[x]; // 上一波沒解決的部分 // 之前紀錄次高的高度，用意在於這裡！ // 當y的最高高度來源是x， // 此時y的次高高度，對x來說才是由y過來的高度。 if (c1[y] == x) record(x, h2[y] + 1, y); else record(x, h1[y] + 1, y); } for (int y=0; y<9; ++y) if (adj[x][y]) if (y != p[x]) DFS2(y); } void balanced_height() { int root = 0; // 隨便挑一點當作樹根皆可 p[root] = root; DFS1(root); DFS2(root); int b_height = 1e9; int diameter = 0; // 順便算直徑 for (int x=0; x<9; ++x) { b_height = min(b_height, h1[x]); diameter = max(diameter, h1[x]); } cout << "樹經過平衡之後的高度是" << b_height; cout << "樹的直徑是" << diameter; for (int x=0; x<9; ++x) if (h1[x] == b_height) cout << "可以作為樹根的點為" << x; for (int x=0; x<9; ++x) if (h1[x] == diameter) cout << "可作為直徑的端點有" << x; }

UVa 10459 10939

parent-child relationship (rooted tree)

建立DFS tree或者BFS tree，就可以輕鬆判斷一點是不是另一點的父親。

bool adj[9][9]; int p[9]; // DFS tree void DFS(int x) { for (int y=0; y<9; ++y) if (adj[x][y] && y != p[x]) { p[y] = x; DFS(y); } } bool is_parent_of(int x, int y) { return x == p[y]; } void parent-child(int root) { p[root] = -1; // 輸入相等的xy時，避免造成錯誤。 DFS(root, root); int x, y; while (cin >> x >> y) if (is_parent_of(x, y)) cout << "x是y的父親"; else if (is_parent_of(y, x)) cout << "y是x的父親"; else cout << "xy不是父子關係"; }

ancestor-descendant relationship (rooted tree)

利用DFS的遍歷順序，就可以輕鬆判斷一點是不是另一點的祖先。

bool adj[9][9]; int t1[9], t2[9]; // DFS進入該點的時刻、離開該點的時刻 int t = 0; // 現在時刻 void DFS(int x, int px) // px是x的父親 { t1[x] = t++; for (int y=0; y<9; ++y) if (adj[x][y] && y != px) DFS(y, x); t2[x] = t++; } bool is_ancestor_of(int x, int y) { return t1[x] < t1[y] && t2[x] > t2[y]; } void ancestor_descendant(int root) { t = 0; DFS(root, root); int x, y; while (cin >> x >> y) if (is_ancestor_of(x, y)) cout << "x是y的祖先"; else if (is_ancestor_of(y, x)) cout << "x是y的祖先"; else cout << "xy不是祖孫關係"; }

distance between two nodes

樹上任兩點之間只有一條路徑。由其中一點開始進行DFS或BFS，直到遇見另一點，就得到距離了。程式碼就不提供了。

時間複雜度為一次Graph Traversal的時間。

distance from one node to any nodes

由該點開始進行BFS或DFS即可。時間複雜度為一次Graph Traversal的時間。

int w[9][9]; int d[9]; int p[9]; void DFS(int x) { for (int y=0; y<9; ++y) if (y != p[x] && y != x) { d[y] = d[x] + w[x][y]; p[y] = x; DFS(y, x); } } void distance_to_any_nodes(int source) { d[source] = 0; p[source] = source; DFS(source); }

distance between all arbitrary two nodes

算出所有兩點之間的距離。可以對圖上各點使用Graph Traversal求得，時間複雜度為O(V^2)。

下面要介紹稍微複雜一點的方法。先隨便選定一個樹根，然後利用Least Common Ancestor將路徑分割成兩條，分頭計算兩條路徑的長度。

這裡提供一個實作方式，時間複雜度為O(V^2)。

1. 樹上隨便挑一點作為樹根。
2. 求所有兩點之間的Least Common Ancestor。
3. 求樹根到圖上各點之距離d(‧)。
4. 樹上x點與y點的距離為 (d(x)-d(z)) + (d(y)-d(z))，
   其中z點是x點與y點的Least Common Ancestor。

int w[9][9]; int d[9]; int lca[9][9]; // 圖上所有兩點之間的LCA int dist(int x, int y) { int z = lca[x][y]; return (d[x] - d[z]) + (d[y] - d[z]); } void all_distances() { int root = 0; // 隨便選一個樹根 all_pairs_least_common_ancestor(root, lca); single_source_shortest_paths_in_tree(root, d); int a, b; while (cin >> a >> b) cout << "a點到b點的距離是" << dist(a, b); }

再提供另一個實作方式，時間複雜度也是O(V^2)。

1. 樹上隨便挑一點作為樹根。
2. 求所有兩點之間的Least Common Ancestor。
3. 以top-down recursive DP計算樹上x點與y點的距離：

d(x,y) =
{ 0                    , when x = y
{ w(x, px), d(px, y)   , when y is the ancestor of x
{ w(y, py), d(x, py)   , when x is the ancestor of y
{ d(x,z) + d(y,z)      , otherwise (z is the lca of x and y)

d(x,y)為x點與y點之間的距離
w(x,y)為邊xy的權重。如果邊xy不存在，w(x,y)為無限大。
px為x的父親，py為y的父親。

int w[9][9]; int dd[9][9]; // 任兩點之間的距離 int lca[9][9]; // 任兩點之間的LCA int p[9]; // DFS tree // top-down recursive DP int dist(int i, int j) { int& v = dd[i][j]; if (v is filled) return v; if (i == j) v = 0; else if (i == lca[i][j]) v = w[j][p[j]] + dist(i, p[j]); else if (j == lca[i][j]) v = w[i][p[i]] + dist(p[i], j); else v = dist(i, k) + dist(j, k); return v; } void all_distances() { int root = 0; // 隨便選一個樹根 all_pairs_least_common_ancestor(root, lca, p); set dd[][] not filled; int a, b; while (cin >> a >> b) cout << "a點到b點的距離是" << dist(a, b); }

Least Common Ancestor

一棵有根樹，樹上兩點共同祖先當中，離根最遠、深度最深的那一個祖先，常簡稱為LCA，亦有人稱lowest common ancestor、nearest common ancestor。

求LCA的演算法相當多元，此處先介紹其中一種：求出樹上所有點對的LCA，運用DFS的特性以及Disjoint-set Forest的概念。

bool visit[100]; // DFS當下已拜訪過的點 int DFS(int x) { visit[x] = true; for (each x, y in query) if (visit[y]) query(x, y) = find(y); for (each x, y in tree) if (!visit[y] && adj[x][y]) { DFS(y); p[y] = x; // union(y, x)，並讓x是樹根 } }

這裡是一個簡單的實作。

bool adj[100][100]; // adjacency matrix，儲存一棵樹，假設樹根為第0點。 bool visit[100]; // DFS當下已拜訪過的點 int lca[100][100]; // 任兩點之間的LCA int find(int x) { return x == p[x] ? x : (p[x] = find(p[x])); } int DFS(int x) { visit[x] = true; for (int y=0; y<100; ++y) if (visit[y]) lca[x][y] = lca[y][x] = find(y); for (int y=0; y<100; ++y) if (!visit[y] && adj[x][y]) { DFS(y); p[y] = x; // union(y, x)，並讓x是樹根 } } int main() { for (int i=0; i<100; ++i) p[i] = i; for (int i=0; i<100; ++i) visit[i] = false; DFS(0); // 假設樹根為0 int x, y; while (cin >> x >> y) cout << "x點與y點的LCA是" << lca[x][y]; return 0; }

時間複雜度切成三部份討論：

一、DFS：很明顯的是O(V^2)或O(V+E)，端看樹的資料結構是哪一種。

二、Disjoint-set Forest：直接考慮p[]被設值的次數，總共是O(V^2)次。

三、設定lca[][]的時間共為O(V^2)。

故時間複雜度總共是O(V^2)。

UVa 10938

Modeling

用DFS遍歷，記下到訪次序（作為索引值）以及深度（作為元素值），則可將LCA問題轉換成±1RMQ問題。

建立Cartesian Tree，RMQ問題就可以變成LCA問題。