# AP325-Python 第8章 樹上演算法
「樹上的問題大部分都可以用DP解決，一個變數不夠，就用兩個。」
「好想抖著拖鞋在樹上打扣，從上往下看，好多問題都變簡單了。」
---
這一章介紹樹(tree)，樹既然是一種圖，圖上的演算法例如BFS與DFS當然也都能用在樹上。但樹是特別稀疏的圖又有特殊的性質，所以很多問題在樹上有更好的解。另一方面，許多資料結構是使用樹的觀念建構出來的，本章探討的主要是輸入資料是一個樹的問題，而並非用樹做為資料結構的問題，這兩類問題並不相同。樹上的問題大部分都屬於貪心法則或是動態規劃，但需要搭配樹的結構來處理。
## 基本觀念與名詞
回顧一下圖的基本定義，一個圖寫作$G=(V,E)$，表示一個圖名字是$G$，由點的集合$V$與邊的集合$E$組成，其中$V$是點集合，也就是要研究的對象；而$E$是邊的集合，也就是誰與誰之間存在這種關係。樹(Tree)是一個連通而無環路的圖，通常指的是無向的簡單圖，也就是說若一棵樹$T=(V,E)$，則$m=n-1$，其中$n$與$m$是點數與邊數。
為了方便或需要，我們可以指定其中一點為根(root)，稱為有根樹(rooted tree)，一旦指定根之後，我們可以給圖上的邊訂定方向，每個邊的方向是由根往其他點，或者尤其它點往根的方向。通常把樹畫成一個家族圖，根在最上方，也就是說所有的邊都是一個上下兩點的關係，tree所代表的二元關係就被比喻為parent與child的關係。下圖是一個有根樹，其中0是根。除了根以外，每個點的上方恰有一點與其相連，這個點稱為他的parent，例如4與3的parent是1；而1與2的parent是0(根)。若a是b的parent，則稱b是a的孩子(child)。**只要指出每一個點的parent就可以惟一決定一棵樹**。以下介紹一些基本的知識與名詞。
* 樹的等價定義(定理)：樹的定義是「連通無環路的圖」，以下的敘述也都可以證明所代表的是一棵樹。
* 一個連通圖且$n=m+1$；
* 一個無環路的圖且$n=m+1$；
* 任兩點恰有一條路徑的圖；
* 一個圖，點以1 ~ $n$編號，邊的集合是$\{(i,p(i)): p(i)<i, 2\le i\le n\}$。也就是除了1號點之外，每個點連一條邊到編號比他小的點。這個圖其實就是個有根樹，p(i)就是i的parent，每個點的編號都大於parent的編號。
* 每一個連通區塊都是一棵樹的圖就稱為森林(forest)，也就是說一個森林由若干個不相交的樹組成，有$n$個點的森林，它的邊數是$m=n-k$，其中$k$是連通區塊的個數。
* 在有根樹上，沒有孩子的點稱為樹葉(leaf)，葉子也稱外節點(external node)，不是葉子的稱為中間節點(internal node)。每個點沿著parent往上一路走，都會走到root，中間碰到的點都是它的祖先(ancestor)。對於一個點$v$，所有以$v$為祖先的點，就是$v$的後代(descendant)，$v$與它的所有後代組成的圖就是以$v$為根的子樹(subtree rooted at $v$)。在無根樹上，只有一個鄰居的點也稱為葉節點。
* 有根樹的分支度(degree)通常指每個點孩子數量的上限，degree為2的樹(也就是每個點最多兩個孩子)稱為二元樹(binary tree)，二元樹中每個節點的兩個孩子稱為左孩子與右孩子，以左(右)孩子為根的子樹就稱為左(右)子樹。二元樹在資料結構中扮演重要的腳色，例如二元搜尋樹(Binary search tree)與堆積(heap)，但本章中用到的觀念不多，因此只做簡略的名詞介紹。
* 完整二元樹(Complete binary tree)是指一個二元樹它的葉節點只在最後兩層，而且如果葉節點在倒數第二層的話，一定在最右邊且連續出現，如下圖。完整二元樹如果用由上而下由左至右連續以 1 ~ $n$編號，可以用編號來找parent與child，因此可以用陣列儲存而無需用複雜的資料結構。在右圖的例子中，任一點$v$的左孩子是$2v$而右孩子是$2v+1$，如果這兩個孩子編號沒有超過$n$；$v$的parent是$v//2$(整數除法)。堆積是以完整二元樹的概念建構的，常用來製作優先佇列。
* 二元搜尋樹(Binary search tree, BST)的每一個節點可以存一筆資料，每一筆資料有一個鍵值(key)作為排序的依據，BST的key滿足以下規則：對任何一點$v$，在它左子樹中的點，鍵值必定小於它；在它右子樹中的點，鍵值必定大於它。BST有不同的變化形式，是很重要到的動態資料結構，一個平衡的BST通常樹高不超過$O(\log(n))$，C\++ STL中的set/map通常以平衡的BST建構。
一些其他名詞我們在後面遇到時再說明。因為樹沒有環路，如果從樹上刪掉任意一點，會造成一些獨立的子樹，既然是獨立不相交的，往往就可以獨自求解，然後在該點上合併子問題的解，這事實上就是分治的概念，如果從非遞迴的角度，它就是動態規劃(DP)。實際解題時，為了方便，通常把樹當成有根樹來做，而實作就區分為top-down(遞迴)與bottom-up(非遞迴)兩種方式。所以說樹上的問題絕大部分都可以用DP來解，以下我們會看到很多例子。
## 樹的儲存與基本演算法
在這一節中我們介紹儲存樹的基本資料結構與幾個基本演算法。
儲存樹的資料結構
樹是一種圖，儲存圖的資料結構當然可以用來存樹，但是樹是非常稀疏的圖，所以用鄰接矩陣是非常不合適的。如果是無根樹，用鄰接串列是合適的方式。在有根樹時，我們還有兩種儲存方式：存parent以及存child。使用上當然要看輸入給的方式，也要看程式的寫法。基本上三種方式可以互相轉換。
因為parent與child是相互的關係，如果題目給的是每個點的parent(除了root)，要轉成child的形式，就讓每一個點把自己放進parent的child[]；如果題目給的是child，就由每一個parent設定自己孩子的parent。
以下是簡單的範例，我們寫了兩段程式，一個從parent轉成child，另外一個從child轉成parent。因為Python的list是可變長度的，即使degree沒有限定，list用來儲存graph與tree都是很方便的。
另外需要留意，因為root將來是沒有parent，在實際應用時有不同的表達方式，常用的方法是設成不可能的值(如-1)。這個範例程式只是做簡單的示範說明，實際應用時根據需要調整。
```python=
# tree, data structure demo, parent and child
n = 10 # number of nodes, 0 ~ n-1
# parent to child
# given parent[v] for each v, find child[v] for each v
# initial all empty list
child = [[] for i in range(n)]
for v in range(n):
if parent[v] >=0: # parent[root]=-1
child[parent[v]].append(v)
# child to parent, parent[root] = -1, return root
parent = [-1]*n # initial -1 as no parent
for i in range(n):
for c in child[i]: # each child of i
parent[c] = i
root = parent.index(-1) # parent[root] = -1
```
樹的child或parent儲存形式要轉成無根樹的連接串列形式非常簡單，因為一個點的鄰居就是parent以及所有的child。另一方面，要將無根樹的鄰接串列轉成有根樹的child或parent的形式則須要做一個BFS或DFS走訪，以下介紹BFS與DFS。
### DFS
樹的DFS相當重要，大部分樹的題目都可以用DFS來解。樹既然是圖的一種，當然可以用圖的DFS來做樹的DFS，但另一方面樹是一種特殊而簡單的圖，所以可以更簡單的來做。有根樹與無根樹的走訪很類似，我們先用一個例題來示範無根樹的DFS。
這裡要先說明一個注意事項，DFS通常以遞迴的方式撰寫，Python的遞迴深度是有限制的，即使打開深度限制，遞迴也會使用較多的記憶體，所以有些題目在某些環境是無法以遞迴的方式通過的。這裡建議這一些題目就用後面的Bottom-up方式來寫。
---
##### P-8-1. 樹上的推銷員
有一個推銷員要走訪$n$個城市並在結束後回到出發的城市。這些城市以$n-1$條道路連接，每條道路連接兩個不同的城市並且雙向可以通行，而且已知每一個城市都可以到達，不會有到達不了的狀況。輸入道路的資料，請你找出一個長度最短的城市走訪順序，因為這樣的順序很多，你必須輸出字典順序最小的那一個。字典順序是用來比較兩個序列的先後順序，其方法是由前往後找到第一個不相同的位置，該元素比較小的序列就是順序比較小，如同在英文字典中單字的順序一般。例如
$(0,2,3,1)<(0,3,1,2)$，又$(0,3,2,1)<(1,0,2,3)$。
舉例來說，如下圖，有5個城市以4條道路連接，假設每條道路的長度都是1。字典順序最小的最短拜訪順序是$(0,1,0,4,2,4,3,4,0)$。
Time limit: 1秒
輸入格式：第一行是正整數$n$，代表城市的數量，城市是以0 ~ $n-1$編號，接下來有$n-1$行是道路的資料，每行三個整數$a$,$b$與$w$，代表此道路連接城市$a$與$b$，道路的長度是$w$。$n$不超過50000，每條道路長度是不超過100的正整數。
輸出：第一行輸出最短的旅行距離，第二行輸出拜訪順序，相鄰的數字之間要以一個空白間格。
範例一輸入：
5
1 0 1
0 4 1
2 4 1
4 3 1
範例一輸出：
8
0 1 0 4 2 4 3 4 0
範例二輸入：
3
1 2 5
0 2 3
範例二輸出：
16
0 2 1 2 0
註：本題要示範DFS，測資中遞迴的深度不超過1000。
---
有$n$個城市以$n-1$條道路連接而且每個城市都可以彼此到達，顯示是一個$n$個點$n-1$個邊的連通圖，所以它是個樹。旅行推銷員問題在一般圖上是很難解的問題，我們在第6章DP中有見過，但是在樹上卻相當簡單：**最短的環路一定每個邊恰好走兩次**。
這可以用歸納法很簡單的證明，想像$v$是一個葉節點，$P$是走訪其他$n-1$個城市的最短環路，我們只要沿著$P$走，走到$v$的惟一鄰居時，繞過去$v$就行了。
所以任何一個DFS走的順序都是最短的環路，這一題的問題其實是要找字典順序的DFS。在做圖的DFS時，有一個重點是對每個點需要設定一個visit[]值，來避免重複走訪到已經走過的點，但樹的DFS可以省略這個動作，取而代之的是遞迴呼叫$v$時，傳過去從哪個點($p$)呼叫它，因為樹沒有環路，只要不要遞迴呼叫$p$，就不會重複走訪到同一點。
請看下面的範例程式。$adj[v]$用來存每個點$v$的鄰居，tour是用來放答案的環路。第2 ~ 8行就是DFS的遞迴函數。每次走到$v$我們先將$v$放入tour當做拜訪$v$的動作，接著對它的每個鄰居$u$(除了來時路的$p$)，遞迴呼叫$dfs(u,v,tour)$以拜訪$u$點以下所有點，每一個鄰居拜訪完畢都會回到$v$。
主程式輸入邊時，我們把邊長另外加總處理。輸入完畢後，先將每個點的鄰居依照編號排序，以便找出的順序是字典序最小，然後以dfs(0,-1,tour)作為以0為起點的走訪。
```python=
# lexicographic first dfs
def dfs(v,p,tour): # visit v, parent p
tour.append(v) # first arrive v
for u in adj[v]:
if u == p: continue
dfs(u,v,tour) # visit u
tour.append(v) # back to v
return
#
n = int(input())
adj = [[] for i in range(n)]
total = 0
for i in range(n-1):
u,v,w = [int(x) for x in input().split()]
total += w
adj[u].append(v)
adj[v].append(u)
# sort adj
for i in range(n):
adj[i].sort()
tour = []
dfs(0,-1,tour)
print(total*2)
print(*tour)
```
這一題以無根樹的走訪來做就可以，但是為了示範有根樹的DFS，我們也寫一個將無根樹轉換為有根樹之後再做DFS的範例程式，請看以下程式。
誠如上面所說，這個程式基本上是DFS走兩次。函數$root(v,p,child)$是做將樹以 $v$ 點為root吊起來的動作，除了$p$以外的所有鄰居都變成$v$的$child$。並且對每一個$v$的孩子$u$，遞迴呼叫$root(u,v,child)$，這樣完成了無根樹轉成有根樹的動作。
然後在將各點的child排序後，呼叫$tsp(0,tour)$來進行以0點開始的DFS走訪。因為已經轉成有根樹，遞迴走訪的函數$tsp(v)$不需要指名parent是誰，先拜訪$v$點後對每一個孩子$u$，進行遞迴拜訪$tsp(u,tour)$以及回到$v$的動作。
```python=
# lexicographic first dfs, transform to rooted tree
# rooting at v with parent p
def root(v,p,child):
for u in adj[v]:
if u != p:
child[v].append(u)
root(u,v,child)
return
def tsp(v,tour): # visit v, parent p
tour.append(v) # first arrive v
for u in child[v]:
tsp(u,tour) # visit u
tour.append(v) # back to v
return
#
n = int(input())
adj = [[] for i in range(n)]
total = 0
for i in range(n-1):
u,v,w = [int(x) for x in input().split()]
total += w
adj[u].append(v)
adj[v].append(u)
# rooting at 0
child = [[] for i in range(n)]
root(0,-1,child)
# sort child
for i in range(n):
child[i].sort()
tour = []
tsp(0,tour)
print(total*2)
print(*tour)
```
這是本章第一個樹的DFS，請務必了解，雖然Python因為遞迴的關係，解題要避免DFS，但將來如果學習其他語言時，例如C\++，樹的問題大部分都是利用DFS的架構去做的。
### BFS
樹上的BFS與DFS一樣的都是由起點往外走，如果把起點當root，那麼兩者走出來的順序固然不同，但都是一個top-down的順序，也就是任何一點都在它的孩子之前被拜訪，如果把這個順序反過來，就是一個Bottom-up的順序。樹的問題有很多都是DP或貪心法則，而都需要一個top-down或bottom-up的順序，DFS通常用遞迴的寫法，而BFS用非遞迴，雖然遞迴比較好寫，但是Python的遞迴往往不允許，所以寫BFS較好。
在圖的時候，BFS還有一個必要是在無加權圖上求起點到個點距離，這個問題在樹上略有不同，因為樹沒有環路，不管是加權圖或是非加權圖，都可以用DFS或BFS來計算起點到個點的距離。
對於其他語言(例如C)來說，樹上用BFS的機會比較少，如果遞迴可用，通常用DFS；但對於Python而言，因為遞迴的限制，測資太大不可用DFS，解題時盡量還是BFS來做比較保險。
我們以起點到各點的距離來展示樹上的BFS。
---
##### P-8-2. 物流派送系統
有一個物流派送系統，系統有$n$個工作站與$n-1$條輸送帶，工作站以0 ~ $n-1$編號，其中0號站是進貨站，所有物品都是由0號站進入系統然後經過輸送帶配送到某個站。每個輸送帶都是單向的從某個站$a$把物品送到站$b$，輸送的時間是$w(a,b)$。已知由進貨站可以經由輸送帶直接或間接轉送到達任何其他站，請計算下列兩者
(1). 由進貨站到達運送時間最長的站需要多少時間，以及
(2). 由進貨站需要最多次轉運的需要經過幾次輸送帶。
舉例來說，如上圖，有5個站以4條輸送帶連接，假設每條輸送帶的運送時間如圖上標示。需要最長運送的時間是3號站(2+4=6)，最多需要經過的輸送帶是兩次(2號站與3號站)。
Time limit: 1秒
輸入格式：第一行是正整數$n$，$n>1$，接下來有$n-1$行是輸送帶的資料，第$i$行，$i\ge 1$，有2個整數$x$與$w$，代表此輸送帶連接$x$與$i$，輸送的時間是$w$。$n$不超過1e5，每條輸送帶的輸送時間是不超過1000的正整數。
輸出：第一行輸出最長的運送總時間，第二行輸出最多經過幾次輸送帶。第一行與第二行的答案不一定是同一個站，除了輸送帶以外的時間均忽略不記。
範例一輸入：
5
0 5
4 1
4 4
0 2
範例一輸出：
6
2
範例二輸入：
6
0 9
0 1
2 1
5 3
3 2
範例二輸出：
9
4
範例一：題目中的例子
範例二：時間最久的是0->1，時間是9；最多次的是0->2->3->5->4，共四次。
(測資1與2的$n\le 100$且前一站的編號必然小於該站。)
---
工作站是點，輸送帶是邊，$n$個點$n-1$個邊，而0可以到達所有的點，這個圖形就是一個有根樹，邊有長度，第一個要求的是根到各點的最大距離，第二個是經過最多次的邊，那也就是無加權圖的最大距離。輸入給的形式是每個點的前一站，也就是parent。
在樹上計算根(0)到所有v的距離其實不過就是個簡單的DP，遞迴式
$d[v] = d[parent[v]] + w(parent[v],v)$ for all $v > 0$
所以只要找出所有點都出現在它parent之後的top-down序列，然後根據遞迴式計算即可，以下是這樣寫的範例程式。在輸入的時候，除了parent之外，我們也轉存每個點的child(第9行)，各點$i$到它parent之間的邊長則存在$leng[i]$。第12行啟用一個list que當作queue來使用，然後開始一個BFS走訪，因為是tree，我們不需要記錄該點是否已拜訪過，所以while迴圈中只是簡單的從queue中取出一點，然後將它的孩子都放進queue的尾端。
接著第18 ~ 20行計算最遠的加權距離，只要沿著順序套遞迴式計算就可以了，最後是無加權圖的距離，我們放在$step[v]$，它的算法相同，只是每個邊都算1罷了。
```python=
# P-8-2 longest distance d(0,v), BFS, two pass
n = int(input())
child = [[] for i in range(n)]
leng = [0]*n
parent = [-1]*n
for i in range(1,n):
v,w = [int(x) for x in input().split()]
parent[i] = v
child[v].append(i)
leng[i] = w # length of edge (parent[i],i)
# find a top down sequence
que = [0]; head = 0
while head < len(que):
v = que[head]; head += 1
que += child[v]
#
# compute distance in top-down sequence
d = [0]*n
for v in que[1:]: # except root que[0]
d[v] = d[parent[v]] + leng[v]
step = [0]*n
for v in que[1:]:
step[v] = step[parent[v]] + 1
print(max(d))
print(max(step))
```
其實找順序與計算距離可以在同一回合做，就像標準的BFS一樣。以下就是這樣的寫法。
```python=
# P-8-2 longest distance d(0,v), BFS, two pass
n = int(input())
child = [[] for i in range(n)]
leng = [0]*n
#parent = [-1]*n
for i in range(1,n):
v,w = [int(x) for x in input().split()]
# parent[i] = v
child[v].append(i)
leng[i] = w # length of edge (parent[i],i)
# find a top down sequence
d = [0]*n
step = [0]*n
que = [0]; head = 0
while head < len(que):
v = que[head]; head += 1
for u in child[v]:
d[u] = d[v] + leng[u]
step[u] = step[v] + 1
que.append(u)
#
print(max(d))
print(max(step))
```
如同前面說的，tree上找距離也可以用DFS，DFS用遞迴也不需要queue，所以確實更簡潔。但後兩筆測資在某些系統環境下可能無法執行。
```python=
# P-8-2 longest distance d(0,v), dfs
def dfs(v):
global d,step
for u in child[v]:
d[u] = d[v] + leng[u]
step[u] = step[v] + 1
dfs(u)
#
n = int(input())
child = [[] for i in range(n)]
leng = [0]*n
for i in range(1,n):
v,w = [int(x) for x in input().split()]
child[v].append(i)
leng[i] = w # length of edge (parent[i],i)
#
d = [0]*n # distane frm root
step = [0]*n # number of edge from root
dfs(0) # starting from root 0
print(max(d))
print(max(step))
```
### 由下而上的走訪
由下而上計算是很多樹的演算法所需要的順序，如果遞迴可以用，通常優先使用DFS，如果不行，就必須自己找一個Bottom-up順序。非遞迴的找此順序可以採用上一節的BFS，因為將top-down順序反轉過來就是bottom-up順序。但這樣需要先找順序再做計算，通常要兩回合。
有時我們希望一個回合直接一面找順序一面做計算，我們在P-3-1已經介紹過這樣的做法了，其實就是把樹看成一個由下而上的DAG。我們準備一個queue放置已經可以出列的點，一開始把所有葉節點都放進queue，每一回合從queue中取出一點，將它的parent的孩子數減一，若它的parent變成葉子，就放進queue中。
我們以下一個題目來展示bottom-up序列的計算與運用。
---
##### P-8-3. 購物中心選位置
有$n$個小村莊以0 ~ $n-1$編號，其中編號0的是市政府所在地，這些村莊以$n-1$條道路連接，每條道路都是雙向通行且連接兩個不同的村莊，已知從任一個村莊 $i$ 都可以經由這些道路到達市政府所在的 0 號村莊，所以也可以到達任何其他村莊，而且由村莊 $i$ 往市政府會經過的第一站村莊是$p(i)$。現在某大集團希望選其中一個村莊來蓋一個購物中心，選址的判斷方式是購物中心到所有村莊的距離總和要越小越好，請你幫忙計算哪一個村莊是最好的位置，到各村莊的距離總和最小是多少。
Time limit 2 秒
輸入格式：第一行是正整數$n$，$n>1$，村莊以 0 ~ $n-1$ 編號。接下來有$n-1$行是道路的資料，$i$由$1$到$n-1$，第$i$行有2個整數$p(i)$與$w(i)$，代表$i$往$0$號村莊的道路第一個會經過$p(i)$，而$i$與$p(i)$之間的道路長度是$w(i)$。$n$不超過1e5，每條道路的長度是不超過1000的正整數。
輸出：第一行輸出最佳的村莊編號，如果有超過一個村莊都是最佳位置，則找離市政府最遠的那一個，第二行輸出最佳村莊到各村莊距離總和。
範例一輸入：
5
0 5
4 1
4 4
0 2
範例一輸出：
4
14
範例二輸入：
6
0 9
0 1
2 1
5 3
3 2
範例二輸出：
3
21
範例一說明：最佳位置是4號村莊，4到其它村莊的距離總和是14。
範例二說明：2與3到其它的距離總和都是最小的21，而3離0的距離比2與0的距離遠。
---
這些村莊與道路構成的圖顯然是個樹，$p(i)$就是$i$的parent，0號點是root。令$D(v)$是點$v$到所有其他點的距離總和，對任一點$v$，我們可以在$O(n)$的時間計算出$D(v)$，所以對每一點$v$都求出$D(v)$來再找最小值的方法可以在$O(n^2)$完成，但是還是不夠快，因為本題要求的$n$是1e5。
假設這些點是在一條數線上，也就是$n$個數字要找其中一個與其它數字的距離總和最小，那麼答案是這$n$個數字的中位數(median)，也就是排序後位置在中間的那個數字，如果$n$是偶數，則中間那兩個都是解(到各點距離相同)。這個證明其實很簡單，對於任意一點，如果他的左右有一邊的點數超過$n/2$，例如左邊有$x$個點，$x > n/2$，則將點往左邊移動長度$y$，左方$x$個點距離減少$xy$，右邊$(n-x)$個點距離增加$(n-x)y$，總距離一定會減少。所以所選的點左右兩邊的點數都不會超過$n/2$。
在圖上與其它點距離總和最小的點也是稱為median。樹的median與數字的median有一樣的性質，事實上數線上的點就是樹的退化情形。若$v$是$D(v)$最小的$v$點，則$v$的每一個分枝的點數都不會超過$n/2$。這一題的輸入給的方式是以0為root的有根樹，因此找median其實是要找子樹的點數。令$num(v)$是以點$v$為根的子樹的點數，也就是$v$的後代總數(含$v$自己)，我們要找的是”最低”的某個點$s$，滿足$num(s)\ge n/2$，最低的意思是，對所有$s$的孩子$c$，$num(c)< n/2$。如果$num(s)$恰好是$n/2$，則$s$與其parent都是median，根據本題的題意，此時要輸出比較低的那一個median。請注意，數學上「$\ge n/2$」在程式中必須寫成「>= (n+1)//2」，因為整數除法捨位的關係。
所以本題最主要的是算各子樹的大小$num(v)$，算完之後，可以依照定義找某個點，它的孩子的子樹都不到$n/2$而它的子樹不小於$n/2$，最後再計算到其他點距離。
至於計算各子樹的大小的方法，以下是一種想法：因為每個點都是它每個祖先的後代，沿著parent一路往上走碰到的都是祖先，所以，我們可以對每個點都把他加到它所有的祖先中。以下是這樣寫出來的程式，整個程式分兩段：找出median，然後計算median到各點的距離。
一開始先做輸入，第9行的$num[v]$就是放$v$點以下的子樹的點數；第10 ~ 14行是對每一個點，沿路往上將所有祖先都加一。根據前面的說明，median就是沒有孩子的家族>=(n+1)//2，而自己的家族>=(n+1)//2。所以第15 ~ 18行先檢查有無孩子有大家族，然後第19 ~ 21行再跑一個迴圈找出median。
第二部分要算距離，我們採取BFS的方式，先將parent關係轉成unrooted的adj形式，然後第30 ~ 38行走一個BFS算距離，此處我們以d[v]=-1表示沒有算過。
```python=
# P-8-3 tree median, O(nh) method
# find medium
n = int(input())
parent = [-1]*n
leng = [0]*n
for i in range(1,n):
parent[i],leng[i] = [int(x) for x in input().split()]
# find num(v): number of nodes in subtree rooted at v
num = [0]*n
for i in range(n):
v = i # add all its ancestor by 1
while v >= 0:
num[v] += 1
v = parent[v]
big_child = [False]*n # if having a child >=n/2;
for i in range(1,n):
if num[i] >= (n+1)//2:
big_child[parent[i]] = True
median = 0
while num[median] < (n+1)//2 or big_child[median]:
median += 1
# median: the only one >= (n+1)//2 and no big_child
# compute d[v] the distance from median to v
#transform to unrooted adj
adj = [[] for i in range(n)]
for v in range(1,n):
adj[v].append((parent[v],leng[v]))
adj[parent[v]].append((v,leng[v]))
# compute d by bfs
d = [-1]*n # distance from median, -1 as uncomputed
que = [median]; head = 0
d[median] = 0
while head < len(que):
v = que[head]; head += 1
for u,w in adj[v]:
if d[u] < 0: # uncomputed
d[u] = d[v]+w
que.append(u)
#
print(median)
print(sum(d))
```
這個程式的主要缺點是在找median的部分算得太慢，複雜度太差，如果樹的高度是$h$，需要的時間是$O(nh)$，所以在樹高是$O(n)$時，它的時間複雜度是$O(n^2)$。
其實，根據定義：$num(v)=1+\sum_{u\in child(v)} num(u)$，因此計算$num(v)$不過就是個類似於前綴和的簡單DP，只要走一個bottom-up的順序，當一個點的子樹大小算好了之後，把它加到parent的子樹大小中就可以了。這樣做足夠改善複雜度，但是程式還是比較複雜囉嗦，子樹大小都算好了，是不是可以用來計算要算的距離呢？
若$m$是median，我們要算$m$到所有點的距離和，直接的方法當然是把每一條路徑都算出來再加總，其實在樹上有另外一種計算方式。考慮任一條邊$(u,v)$，其中$v$是$u$的parent，邊$(u,v)$把樹分成兩塊，姑且稱為下方與上方，點$m$在$(u,v)$的某一方，那麼，哪些點到$m$的路徑會經過$(u,v)$呢？當然是$m$另外一方的點才需要跨過此邊，所以我們只要知道另外一方有幾點，就知道$(u,v)$在距離總和中會被計算多少次，對每個邊都這樣計算後加總就是距離總和了。
那麼，$m$在哪一方？根據median的性質，$m$一定在點多的那一方！！我們在計算$num[]$時算出了每一個子樹的大小，所以我們知道$num[u]$，不管$m$在上方或下方，這條邊被計算的次數是$\min(num[u], n-num[u])$。有了這個了解，我們就可以直接算距離總和了。以下是用bottom-up順序做的範例程式。
```python=
# P-8-3 tree median, Bottom-up method, O(n)
n = int(input())
parent = [-1]*n
leng = [0]*n
deg = [0]*n
for i in range(1,n):
parent[i],leng[i] = [int(x) for x in input().split()]
deg[parent[i]] += 1
#
num = [0]*n # number of nodes in subtree rooted at v
median = -1
total = 0 # total distance to median
# bottom-up sequence
que = [v for v in range(n) if deg[v]==0] # all leaves
head = 0
while head < len(que):
v = que[head]; head += 1
num[v] += 1 # add itself
if median < 0 and num[v] >= (n+1)//2:
median = v
total += min(num[v], n-num[v]) * leng[v]
# check parent
p = parent[v]
if p<0: break # root
num[p] += num[v]
deg[p] -= 1
if deg[p] == 0: que.append(p)
#
print(median)
print(total)
```
輸入的時候順便計算每個點的孩子數量$deg[]$，第14行準備一個list que放可以出列的點，初始時把葉節點($deg[]=0$)放入，然後跑一個while迴圈做bottom-up走訪。每次迴圈從佇列中拿出一點$v$來，因為它一定在它的所有孩子之後出列，所以它的孩子們的子樹大小都已經加到它的$num[v]$中了，因為我們尚未算$v$自己，所以將$num[v]$加 1，第19行檢查它是否是第一個超過$n/2$的子樹，初始我們將median設為 -1，所以第19行的if成立時，$v$就是最低的(也就是我們要找的)median。第21行我們計算到median的距離總和中這個邊會被計入的量，接著，將它的$num[v]$加入parent的子樹大小中，並檢查parent是否要進入que中。這個程式要簡潔多了，時間複雜度是$O(n)$。
如果用遞迴當然程式碼更簡潔一點，但本題Python可能會有遞迴過深或記憶體的問題，資料夾中有一支DFS版的範例程式，有興趣的讀者自行參考。
**End of Chapter 8 (I)**
接續 [AP325-Python 第8章 樹上演算法 (II)](/EMOX8rdLRIOcurylpEhyIQ)
Sign in with Wallet
Connect another wallet