**Chapter 8 (II)**
## 例題與習題
在這一節中我們介紹一些典型的樹狀圖的題目，不外乎貪心法或遞迴，也有些是模擬或走訪。下一題曾經出現在P-3-1，當時是介紹由下而上的走訪方式，而且還沒介紹什麼是DP，在學過DP以及樹的DFS之後，這一題應該變得簡單很多了。
---
##### P-8-4. 樹的高度與根 (同P-3-1) (APCS201710)
有一個大家族有$N$個成員，編號1 ~ $N$，我們請每個成員寫下此家族中哪幾位是他的孩子。我們要計算每個人有幾代的子孫，這個值稱為他在這個族譜中的高度，也就是說，編號 $i$ 的人如果高度記做 $h(i)$，那麼 $h(i)$ 就表示在所有 $i$ 的子孫中，最遠的子孫與他隔了幾代。本題假設除了最高的一位祖先(稱為root)之外，其他成員的parent都在此家族中(且只有一個parent)。本題要計算所有成員高度的總和以及根的編號。
上圖是一個例子，每個成員是一個圈起來的號碼，劃線相聯的表示上面的點是下面點的parent。編號4是根，有兩個孩子1與7。編號6, 9, 3, 8都沒有孩子，$h(6)=h(9)=h(3)=h(8)=0$，此外
$h(2)=2$因為9與他隔兩代。你可以看出來$h(5)=h(1)=1$，$h(7)=3$, $h(4)=4$，所以高度總和是11。
Time limit: 2秒
輸入格式：第一行有一個正整數 $N$。接下來有 $N$ 行，第 $i$ 行的第一個數字 $k$ 代表 $i$ 有 $k$ 個孩子，第 $i$ 行接下來的 $k$ 個數字就是孩子的編號。每一行的相鄰數字間以空白隔開。$N \le 1e5$。本題測資保證最大高度不超過1000。
輸出：第一行輸出根的編號，第二行輸出高度總和。
範例輸入：
9
1 6
3 5 3 8
0
2 1 7
1 9
0
1 2
0
0
範例結果：
4
11
註：本題雖與P-3-1題序相同，但測資保證不會超過Python的遞迴深度。
---
因為一個點的高度，是他所有孩子最高的高度加一，這是一個遞迴定義，使用DFS來做就非常簡單，先找到root，從root進行DFS，在每一個節點時，對每一個孩子呼叫一次高度計算，然後在所有孩子中取最大值加一就是該點高度了。
```python=
# tree height O(n), dfs
def findh(r,h): # dfs
h[r] = 0
for v in child[r]:
findh(v,h) # recursive call
h[r] = max(h[r], h[v]+1)
#
n = int(input()) #
child = [[] for i in range(n+1)]
h = [0]*(n+1) # height of node i
not_root = [True]+[False]*n # 1-index
for v in range(1, n+1):
# ignore the first one
child[v] = [int(x) for x in input().split()][1:]
for u in child[v]:
not_root[u] = True
# find root
root = not_root.index(False)
findh(root,h) # dfs starting from root
print(root)
print(sum(h))
```
如果只做純遞迴，時間複雜度會變成$O(nh)$，其中$h$是樹的高度，下面是一個寫壞的方式。
```python=
# tree height O(n), pure recursion O(nh)
def findh(r): # return height of r
height = 0
for v in child[r]: # recursive call
height = max(height,findh(v)+1)
return height
#
n = int(input()) #
child = [[] for i in range(n+1)]
not_root = [True]+[False]*n # 1-index
for v in range(1, n+1):
child[v] = [int(x) for x in input().split()][1:]
for u in child[v]:
not_root[u] = True
# find root
root = not_root.index(False)
total = 0
for v in range(1,n+1):
total += findh(v)
print(root)
print(total)
```
純遞迴的時間複雜度會差，是因為我們沒有把做過的事情用表格記錄下來，如果用top-down DP的觀念，使用表格紀錄，即使對每個點呼叫一次，時間複雜度依然只有$O(n)$。下面是不懂樹但是懂top-down DP的寫法。
```python=
# tree height O(n), top-down dp O(n)
def findh(r,h): # return height of r
if h[r] >= 0: return h[r] # memoization
h[r] = 0
for v in child[r]: # recursive call
h[r] = max(h[r],findh(v,h)+1)
return h[r]
#
n = int(input()) #
child = [[] for i in range(n+1)]
not_root = [True]+[False]*n # 1-index
for v in range(1, n+1):
child[v] = [int(x) for x in input().split()][1:]
for u in child[v]:
not_root[u] = True
# find root
root = not_root.index(False)
total = 0
h = [-1]*(n+1) # memo, -1 as uncomputed
for v in range(1,n+1):
total += findh(v,h)
print(root)
print(total)
```
就解題的目的，DFS版本最簡單，但如果在遞迴的限制下，建議採取P-3-1時介紹的Bottom-up解法比較好。一個問題我們提出了多個寫法，目的是讓讀者了解其中的道理。下一個問題也出自APCS的考試中。
---
##### P-8-5. 自動分裝 (APCS202002)
某工程公司設計了一個自動分裝的系統。貨物會一個一個的被送進此系統，經過一些切換器的轉送後，會被輸送到 $n$ 個貨箱。系統有$n–1$個切換器與$n$個貨箱。每個切換器有一個入口以及左右兩個出口，切換器的出口會接到其他切換器或是連接到貨箱，貨箱則只有入口。下圖是一個$n=7$的例子，圓代表切換器，方形代表貨箱，請注意編號1 ~ $n–1$的裝置是切換器，貨箱編號是 $n$ ~ $2n–1$，且貨物入口一定是1號切換器的入口。
每一個切換器會分別記錄左右兩個出口所通往貨箱的總重量，當貨物進入此切換器時，切換器會將貨物轉送到「貨箱總重量比較輕的那個出口」，如果兩邊一樣重，則送往左邊。
以上圖的例子來說，假設每一個貨箱目前的重量如各矩形下方的標示，下一個到達的貨物的運送過程如下：一號切換器左邊出口是連到 {13, 10, 7} 三個貨箱，目前總重5+6+9=20；右邊出口連到的是 {12, 8, 11, 9} 四個貨箱，目前總重7+2+8+1=18，因此貨物會由右邊出口送到5號切換器。
5號切換器的左邊與右邊的貨箱總重是一樣的（7+2=8+1），因此貨物由左出口送至6號切換器。最後，6號切換器將貨物送到8號貨箱（7>2)。貨物進入貨箱後就存放在該貨箱，該貨物的重量就會加入該貨箱的總重，因此可能影響下一個貨物的運送路徑。
輸入此系統的連接架構與貨箱目前的重量，以及接下來依序進入的 $m$ 個貨物的重量，請計算這 $m$ 個貨物分別會被送到哪一個貨箱。
Time limit: 2 秒
輸入格式：第一行為兩個正整數$n$ 和$m$，其中$n \le 1e5$且$m \le 100$。第二行有$n$ 個非負整數，依序是編號為$n$ ~ $2n–1$各個貨箱初始的重量。第三行是$m$個正整數，代表接下來依序進入的貨物重量。全部貨箱初始的重量與貨物重量總和不會超過1e9。第四行開始有 $n–1$ 行，這些是系統架構的資訊：每一行有三個整數$p$、$s$與$t$，代表裝置$p$的左右出口分別接到裝置$s$與$t$，其中$p$一定是一個切換器的編號$(1\le p <n)$。同一行數字之間以空白間隔。
輸出：輸出一行有$m$個整數，依序代表接下來進入系統的$m$個貨物所進入到的貨箱編號，數字之間以一個空白間隔。
範例一：輸入
4 5
0 0 0 0
5 3 4 2 1
1 2 3
2 4 5
3 6 7
範例一：正確輸出
4 6 7 5 5
範例二：輸入
7 2
9 2 1 6 8 7 5
2 3
1 2 5
2 3 7
3 13 10
4 11 9
6 12 8
5 6 4
範例二：正確輸出
8 7
範例二的架構即是題目中的圖。
---
本題所描述的系統其實是一個所謂的二元樹(binary tree)的結構，每一個切換器是一個中間節點(internal node)，每一個貨箱是一個葉節點(leaf node)。題目的要求是模擬每一個貨物進入後的流程，要知道貨物在每個切換器會流向左方或右方，我們需要知道左邊與右邊貨箱總重量。假設知道每個切換器左右的總重量之後，我們就可以依照題意模擬貨物流向，而且根據流向來更新左右總重，所以在下一個貨物進入時，就可以繼續模擬的動作。
所以解這個題目需要會做3件事：
1. 儲存此樹狀結構；
2. 會計算初始每個中間節點左右的總重量；
3. 模擬流程更新重量紀錄。
這一題是二元樹，只要存每點的左右孩子編號就可以了。對於一棵有根樹的某個中間節點，其下的所有節點稱為子樹(subtree)，因此我們需要計算的其實是以每個點為根的子樹重量。計算子樹重量的方法我們在P-8-3算median的時候已經看過了，這一題的中間節點本身是沒有重量，所以是計算子樹中的葉節點重量總和，但做法沒有不同。
我們來看看模擬的流程。對於每個中間點$v$，令$w[v]$為其下貨箱總重，$LC[v]$與 $RC[v]$分別是他的左右子節點的編號。根據題目的定義，中間節點的編號皆小於$n$，因此我們的流程可以描述如下：
```python
# 進入貨物的重量為x，計算其最後到達的貨箱
v = 1; # 進入點(root)的編號
while v < n: # 尚未到達貨箱
if w[LC[v]] <= w[RC[v]] then
v = LC[v] # 左邊較輕往左流
else
v = RC[v] # 往右流
end if
w[v] = w[v] + x # 更新總重
end while
輸出v # 到達的貨箱編號
```
下面的範例程式是以Bottom-up的走訪順序來計算各子樹的重量，因為是二元樹，所以每個節點儲存左右孩子($lc[v]$, $rc[v]$)就可以，我們也儲存parent的資訊在$p[v]$，第13 ~ 23行是在走一個bottom-up順序，並在走訪中把孩子的重量加入parent的重量。
第25行開始模擬每一個進來的貨箱傳送的路線，一面根據左右的重量選擇方向，一方面更新重量。
前半部計算重量的時間複雜度是$O(n)$，後半部模擬的時間複雜度是$O(mh)$，其中$h$是樹的高度。
```python=
# P-8-5 Bottom-up to find subtree weight
n, m = map(int, input().split())
# 1 ~ n-1 are internal nodes, 0 is dummy
w = [0]*n + [int(x) for x in input().split()]
seq = [int(x) for x in input().split()] # incoming aequence
lc,rc = [-1]*(2*n), [-1]*(2*n) #left and right child
p = [0]*(2*n) # parent, p[root=1] = 0 (dummy)
for i in range(n-1): # input tree
s, l, r = map(int, input().split())
lc[s] = l; rc[s] = r
p[l] = p[r] = s
# find weights
deg = [2]*n # num of children of internal node
que = list(range(n, 2*n)) # FIFO queue, initial leaves
head = 0 # head of queue
while head < len(que): # while queue is not empty
v = que[head]; head += 1 # pop from que
if v==1: break # root
u = p[v]
w[u] += w[v]
deg[u] -= 1
if deg[u] == 0:
que.append(u)
#start simulation
out = [] #
for wi in seq: # incoming weight
v = 1
while v < n: # internal node
if w[lc[v]] <= w[rc[v]]: # go left
v = lc[v]
else: v = rc[v] # go right
w[v] += wi
out.append(v)
#end for
print(*out)
```
下面一題是一個裸題，要算樹上所有點到所有點的距離。$O(n^3)$當然不能接受，$O(n^2)$也不行，需要一個$O(n)$的算法。這一題當做習題，給一個提示：請看看P-8-3題中計算median到所有點的距離和所使用的方法。
---
##### Q-8-6. 樹狀圖的距離總和
輸入一個樹狀圖，請計算所有點到所有點的距離總和。本題假設編號1是根節點。
Time limit: 1秒
輸入格式：第一行是正整數$n$，代表點數，點以1 ~ $n$編號，第二行有$n-1$個正整數，$p(2), p(3), …,p(n)$，依序是編號2 ~ $n$ 各點的parent，第三行有$n-1$個正整數，依序代表$i$從2到$n$，邊$(i,p(i))$的長度。$n$不超過1e5，每條邊長度是不超過1000的正整數。
輸出：各點到各點的距離總和。請注意$$到$j$與$j$到$i$都要納入總和，如範例。
範例一輸入：
4
1 2 3
10 20 30
範例一輸出：
400
範例二輸入：
5
1 1 1 2
20 20 30 30
範例二輸出：
880
---
---
##### P-8-7. 寶石的顏色 (108全國高中賽)
尋寶之旅的遊戲有一個地圖，地圖上有$n$ 個站，以0到$n – 1$ 編號，此外有$n – 1$條道路，這些道路都是單向的，遊戲固定從0號站出發，且已知從0號站出發可以直接或間接到達任何其他站。每一個站都有一顆寶石，寶石有分為多種顏色，第 $i$ 站存放的寶石顏色為$c(i)$。出發之前，你可以選定一種顏色的寶石收集箱，路途中遇到與你的收集箱相同顏色的寶石就可以收集(包含起點)，請你計算最多可以收集到多少顆同色寶石。
Time limit: 3秒
輸入格式：第一行有是一個正整數$n$， $n \le 2e5$，代表地圖上有$n$ 個站。第二行是$n$ 個非負整數，依序代表每一站的寶石顏色號碼$c(0), c(1), …, c(n – 1)$；寶石的顏色號碼不超過1e9。接著有$n–1$行，每行兩個以空白間隔的整數$s$與$t$，表示有一條$s$到$t$的道路。測資保證最長路徑不超過990。
輸出：輸出爲一整數，代表最多可能收集到的寶石數量。
範例一輸入：
6
0 0 0 0 0 0
0 1
1 2
0 3
1 4
1 5
範例一輸出：
3
範例二輸入：
10
5 3 3 1 4 0 3 4 5 0
0 1
5 2
7 3
5 4
0 5
4 6
1 7
0 8
4 9
範例二輸出：
2
(測資檔案中，第一筆測資只有一色，第二筆測資不超過10個顏色。另本題為Python更改測資，路徑長度限制在990以下。)
---
樹的每個點上有一個顏色，要選擇一個顏色，並且找出一條由根走到某個葉子的路徑，經過所選顏色的點數越多越好。先想比較簡單的例子，如果只有一種顏色，那就是找一個最長的路徑，因為只能由根往下走，也就是找出根的高度。在P-8-4我們做過如何計算樹的高度。把計算高度的程式稍微修改一下，只有同色的點才計算，很容易就可以計算一條路徑上某個顏色的點有多少，如下面的做法。
```python
# max num of nodes of color col in a path
def dfs(v, col):
nc = 0
for u in child[v]:
nc = max(nc, dfs(u,col))
return nc + (c[v]==col)
#
```
在多種顏色的狀況下，一個簡單的做法是把每一種顏色都算一算，但是時間複雜度會是$O(Cn)$，其中$C$是顏色種類數量。同樣的路走那麼多次實在不聰明，我們可以準備一張表格，紀錄目前的路徑上，各種顏色的數量。DFS過程中，每次走到一點，就將該點顏色數量加一；當DFS返回parent時，我們可以把該點顏色數減一，以表示回復沒有走到他的狀態。這樣看起來表格很容易維護，但是要如何找最多顏色呢？
如果我們在表格上找最大值，又需要花$O(C)$的時間，如果我們聰明一點只有在葉節點才計算最大值，可能可以減少一點時間，但是葉節點的數量可能會高達$O(n)$，所以還是不好。
其實很簡單，在每個節點時，我們不必去看所有的顏色，因為只有該點的顏色數量有變動，所以只要檢查該點的顏色數量有沒有超過最大值就可以了。
最後還有一個問題，顏色的編號並非由0或1連續編號，而是10億以內的非負整數，這表格要如何做呢？其實我們前面已經看過了，這就是要做離散化(P-2-2)。有多種方式可以做離散化，先將他們轉換成0 ~ $C-1$也可以，另外一種方法是使用字典。因為字典的使用可能超過APCS的範圍，下面的範例程式我們先示範用離散化的方法，再提供使用字典處理顏色編號的方法。
```python=
# rooted tree, find a path with max same color
# DFS, coordinate compression
from bisect import bisect_left
def dfs(v):
global cnt,maxc,col
cnt[col[v]] += 1
maxc = max(maxc,cnt[col[v]])
for u in child[v]:
dfs(u)
cnt[col[v]] -= 1 # recover
return
n = int(input())
col = [int(x) for x in input().split()]
# coordinate compression
allc = [-1] # dummy -1, all different color
for c in sorted(col):
if c != allc[-1]:
allc.append(c)
for i in range(n):
col[i] = bisect_left(allc,col[i])
m = len(allc)
child = [[] for i in range(n)]
for i in range(n-1):
p,v = [int(x) for x in input().split()]
child[p].append(v)
#
cnt = [0]*m
maxc = 0
dfs(0)
print(maxc)
```
上面的程式中，第16 ~ 21行就是做離散化(座標壓縮)的動作，我們這麼做的原因是要使用一個表格來當計數器，而必須用顏色的編號當索引，因此顏色編號的範圍不能太大。如果用字典來做，就沒有這個問題了，以下是範例程式，其中cnt是個字典來當做計數器。
```python=
# rooted tree, find a path with max same color
# DFS, with dict
def dfs(v):
global cnt,maxc,col
if col[v] in cnt: cnt[col[v]] += 1
else: cnt[col[v]] = 1
maxc = max(maxc,cnt[col[v]])
for u in child[v]:
dfs(u)
cnt[col[v]] -= 1 # recover
return
n = int(input())
col = [int(x) for x in input().split()]
child = [[] for i in range(n)]
for i in range(n-1):
p,v = [int(x) for x in input().split()]
child[p].append(v)
#
cnt = {}
maxc = 0
dfs(0)
print(maxc)
```
在圖論中，一群不相連的點稱為獨立集(independent set)，在一般圖上找獨立集是件困難的事情，但是在樹上找獨立集並不困難。下面是一個相關的題目。
---
##### P-8-8. 樹的最大獨立集
輸入一棵有$n$個點的樹，我們要挑選一群彼此不相鄰的點，而且挑選的點越多點越好。請計算最多可以挑多少點。以下圖為例，我們可以挑{ 0, 3, 4, 5, 6, 7 }共6點，沒有辦法挑出更多的不相鄰的點。
Time limit: 1秒
輸入格式：第一行是正整數$n$，代表點數，點以0 ~ $n-1$編號，0是根，第二行有$n-1$個正整數，$p(1), p(2), …,p(n-1)$，依序是編號1 ~ $n-1$各點的parent。$n$不超過1e5，相鄰數字以空白間隔。
輸出：最多可以挑選幾點。
範例一輸入：
9
0 0 1 1 2 2 2 6
範例一輸出：
6
範例二輸入：
8
0 1 2 3 3 2 2
範例二輸出：
5
---
若 $T$ 是我們要處理的樹，樹一定有葉，假設$v$是一個葉。我們宣稱：一定有一個最大獨立集挑選了$v$而沒有挑選$parent(v)$。
證明：假設某最大獨立集$S$沒有挑選$v$，那麼一定有挑$parent(v)$，否則可以將$v$加入$S$中變成更大的獨立集。我們可以用$v$點取代$S$中的$parent(v)$得到另外一個獨立集$S’$，就是我們宣稱包含$v$的最大獨立集。這樣的替換不可能造成不合法的解，因為$v$點是葉子，$parent(v)$是它唯一的鄰居。
根據以上的證明，我們可以得到一個貪心法：對於一棵樹，挑選所有的葉節點，捨棄這些葉節點的parent，重複此步驟直到樹被拔光為止。以題目中的樹為例，我們會先挑{3,4,5,8,7}，捨棄{1,2,6}；然後挑0，結束。所得的獨立集是{0,3,4,5,8,7}，與題目中的解雖然不一樣，但都是最大獨立集。
實作時，可以一次拔掉全部的葉子，也可以一點一點拔，因為從葉子下手，所以我們需要一個由下而上的順序，以下是範例程式，程式的重點在於走到每一個點時，必須知道他的孩子中是否有人被挑選，我們用一個陣列chosen[]紀錄每個點是否可以選，初始的時候全設為1，當一個點被挑時，將它的parent的chosen設為0。處理樹的問題要稍微留意root，因為root沒有parent，放在迴圈內處理就必須留意會不會超界或是讀寫到錯誤位置。在這支程式中我們的處理方式是將root在離開迴圈後才處理，當然也有其他方式。
```python=
# P-8-8, unweighted max independent set of a tree
# bottom-up
n = int(input())
p = [-1]+[int(x) for x in input().split()]
chosen = [True]*n
deg = [0]*n # num of children of internal node
for v in p[1:]:
deg[v] += 1
que = list(v for v in range(n) if deg[v]==0)
# FIFO queue, initial leaves
head = 0 # head of queue
total = 0
while head < len(que): # while queue is not empty
v = que[head]; head += 1 # pop from que
if v==0: break # root
parent = p[v]
if chosen[v]:
total += 1
chosen[parent] = False
deg[parent] -= 1
if deg[parent] == 0:
que.append(parent)
print(total+chosen[0]) # root is not counted
```
當然也可以用DFS取代，但Python可能會遭遇遞迴過深的問題，以下是範例程式。
```python=
# P-8-8, unweighted max independent set of a tree
# top-down dfs implement
#return max independent set, un-chosen its parent if chosen
def dfs(v,chosen):
num = 0
for u in child[v]:
num += dfs(u,chosen)
if chosen[v]:
num += 1
chosen[p[v]] = False
return num
n = int(input())
p = [-1]+[int(x) for x in input().split()]
chosen = [True]*(n+1)
child = [[] for i in range(n)]
for i in range(1,n):
child[p[i]].append(i)
#
imax = dfs(0,chosen)
print(imax)
```
下面兩個問題都是與P-8-8類似的題目，我們當做習題。
---
##### Q-8-9. 服務中心選位置
有$n$個小村莊以1 ~ $n$編號，這些村莊以$n-1$條道路連接，每條道路都是雙向通行且連接兩個不同的村莊，已知從任兩個村莊之間都可以經由這些道路通達，兩個村莊稱為鄰近的村莊，如果它們之間有一條道路直接相連。現在要選一些村莊成立服務中心，因為預算的關係無法每個村莊都成立一個服務中心，政府的政策決定：如果某個村莊沒有設服務中心，那麼他一定有一個鄰近的村莊有服務中心。也就是說，任何一個村莊最多只要經過一條道路就可以到達一個有設服務中心的村莊。請你計算至少需要成立幾個服務中心。
Time limit: 2 秒
輸入格式：第一行是正整數$n$，$n>1$，村莊以1 ~ $n$編號。接下來有$n-1$行是道路的資料，每一行有兩個正整數$u$與$v$，代表有一條道路連接$u$與$v$。$n$不超過1e5。
輸出：最少需要成立的服務中心數量。
範例一輸入：
5
1 2
5 1
5 3
5 4
範例一輸出：
2
範例二輸入：
7
1 2
2 3
4 3
5 4
5 6
7 6
範例二輸出：
3
範例一說明：設在{5,2}或{5,1}皆符合要求。
範例二說明：這是7個點排成一條路徑，選{2,5,7}是一個解，兩個點一定無法滿足需求。
---
Q-8-9提示：我們說一個點可以管轄自己與它的鄰居，一個圖上選一些點可以管轄所有的點，這樣的集合稱為管轄集(dominating set)，本題要計算樹的最小管轄集。類似於P-8-8，我們可以想一想：如果$v$是一個葉節點，是否一定有最佳解選了或沒選$v$？當決定選擇某點時，要將它鄰近的點做一些設定。
Q-8-9是比較容易寫壞的題目，下面這一題比較容易。
---
##### Q-8-10. 竊聽間諜網
有$n$個間諜，他們的ID以0 ~ $n-1$編號，間諜頭子的ID是0，除了他以外每個間諜都有一個領導，每個間諜只會與他的領導相互通話，現在我們要竊聽間諜們彼此的通話，所以要在一些間諜的通話裝置上安裝竊聽器，要竊聽到某個間諜與他領導的通話，必須至少在他們其中一人的通話裝置上安裝竊聽器。如果不想漏掉任何通話，至少要安裝幾台竊聽器。
Time limit: 2 秒
輸入格式：第一行是正整數$n$，代表間諜數，每個間諜的ID必定大於他領導的ID。第二行有$n-1$個整數分別是$t(1),t(2),…,t(n-1)$，其中$t(i)$就是$i$的領導。$n$不超過1e5。
輸出：最少的竊聽器數量。
範例一輸入：
5
0 1 1 3
範例一輸出：
2
範例二輸入：
7
0 1 1 1 1 1
範例二輸出：
1
範例一說明：安裝在1號與3號間諜。
範例二說明：安裝在1號間諜。
---
我們說一個點可以cover它所接的邊，在一個圖中選一些點cover所有的邊，這樣的點集合稱為vertex cover，也就是每一個邊的兩端點都至少被選中一點，本題是樹的無權重的minimum vertex cover，與前兩題類似，所以不予提示。
**End of Chapter 8 (II)**
接續 [AP325-Python 第8章 樹上演算法 (III)](/E-EfMMi1Tw6DeoIY-WJzeQ)
Sign in with Wallet
Connect another wallet