**Chapter 8 (III)**
---
##### P-8-11. 公司派對 (NCPC)
有一個公司有$n$個成員，成員以1 ~ $n$編號，每個人都有一個領導，除了編號1是公司的總裁，他沒有領導。現在要辦一個公司派對，想要邀請一些人來參加，如果邀請了編號i的人來參加，就會有$r(i)$的歡樂指數，可是，這個公司的任何人都不想跟他的領導一起參加派對，請你幫忙計算要邀請那些人來參加，才可以讓參加者的歡樂指數的總和最大。
右圖是一個例子，每個圓圈代表一個人，圓圈內的數字是他的歡樂指數，每個人上方與他連線的就是他的領導，你可以看到，總裁的歡樂指數是1，也全公司最低的。我們可以看到此例中有兩個人的歡樂指數是14與11，可惜14是11的領導，所以不能同時邀請這兩人參加。這個例子的最大歡樂指數總和是66，扣除歡樂指數分別為1,3,3,4,14那5個人，其餘的人都參加。
Time limit: 2 秒
輸入格式：第一行是兩個正整數$n$與$r(1)$，接下來有$n-1$行，每行兩個正整數，由$i=2$到$n$，依序是$p(i)$與$r(i)$。$n$不超過1e5，$r(i)$不超過1000的正整數。
輸出：輸出參加派對的最大歡樂指數總和。
範例一輸入：
4 7
1 5
2 6
3 8
範例一輸出：
15
範例二輸入：
15 1
1 5
1 3
1 10
2 14
2 4
3 8
4 3
5 2
5 11
6 2
6 6
8 9
8 6
8 7
範例二輸出：
66
範例一說明：選編號1與4，歡樂指數為7+8=15。
範例二說明：題目敘述中的例子。
---
這一題其實是P-8-8的加權版本，是最大權重獨立集的問題。無加權時要挑選最多不相鄰的點，加權時要挑選總和最大的不相鄰的點。無加權時，貪心法則可以找到最多的點，但是在有加權時，貪心的方法並無法找到最加解，我們嘗試用DP的觀點來找答案。
對任一點$v$，令$f(v)$代表以$v$為根的子樹的最佳解，也就是在$v$的後代(含$v$)中，不相鄰的點最大可能的權重和，但在寫狀態轉移式時候遇到困難，因為$v$點是否有選會影響他的孩子是否可以挑選。碰到類似狀況時，把解分類是通常的解決方法，我們把解分成兩類：
* $f_0(v)$是以$v$為根的子樹中，不挑選$v$的狀態下之最佳解；
* $f_1(v)$是以$v$為根的子樹中，挑選$v$的狀態下之最佳解。
我們可以得到以下遞迴式：
$$
f_0(v) = \sum_{u \in child(v)} \max\{f_0(u),f_1(u)\}
$$
以及
$$
f_1(v) = r(v) + \sum_{u\in child(v)} f_0(u)
$$
也就是說，當$v$不選的時候，他的孩子可以挑也可以不挑；而當$v$被挑選時，他的孩子都不可以挑。根據這個遞迴式，搭配由下而上的DP順序，就可以很容易求解，最後的答案在$\max\{f_0(r), f_1(r)\}$，其中$r$是根。
實作時一樣有bottom-up與top-down兩種寫法，以下揭示非遞迴的寫法，走訪的方式前面已經看過很多次了，就不再多解釋說明，時間複雜度是$O(n)$。
```python=
# P-8-11 Tree, Max weight independent set, bottom-up DP
# f0[], f1[]: opt without/with root
# f0[r]=sum(max(f0[v],f1[v])), f1[r]=w[r]+sum(f0[v])
n, r1 = [int(x) for x in input().split()]
r = [0,r1]+[0]*(n-1) # 1-index
p = [0]*(n+1) # parent
deg = [0]*(n+1)
for i in range(2,n+1):
p[i],r[i] = [int(x) for x in input().split()]
deg[p[i]] += 1
f0 = [0]*(n+1)
f1 = r # using the same list
que = [v for v in range(1,n+1) if deg[v]==0] # leaves
head = 0
while head < len(que):
v = que[head]; head += 1
if v == 1: break # root
u = p[v]
f0[u] += max(f0[v],f1[v])
f1[u] += f0[v]
deg[u] -= 1
if deg[u] == 0: que.append(u)
#
print(max(f0[1],f1[1]))
```
回顧一下在第六章的P-6-2(不連續的表演酬勞)，其實上那就是一個一維陣列的最大獨立集問題，而一維陣列是樹的一種特殊形式，所以也可以仿效P-6-2的解法來想這一題的DP。如果用一維陣列時的解法，還有一種寫法是只設一個遞迴函數$f(v)$是$v$子樹的最佳解，$v$不挑時，選各子樹的解相加；而$v$挑選時，將$v$的孫子(孩子的孩子)為根的子樹的解拿來相加。因為一個點只有一個祖父，這樣做的複雜度還是$O(n)$，所附範例程式中有一支是用這個方法寫的，請自行參考。
下一題在一維陣列中也有類似的題目，當做習題，提示是：請參考P-4-13。
---
##### Q-8-12. 佔領連續的城鎮
某個遊戲中有$n$個城鎮以1 ~ $n$編號，這些城鎮以$n-1$條道路連接，每條道路都是雙向通行且連接兩個不同的城鎮，已知從任兩個城鎮之間都可以經由這些道路通達。現在你要佔領一些城鎮來獲取最大的利益，佔領編號$i$的城鎮可以獲得$w(i)$的利益，但是你佔領的城鎮必須內部可以互相通達，也就是說，若$i$與$j$都是你的領地，則從$i$出發可以只經過你自己的城鎮到達$j$。請計算你最多可以獲得多少總和利益。
Time limit: 2 秒
輸入格式：第一行是正整數$n$，$n>1$，村莊以1 ~ $n$編號。第二行有$n$個整數，依序是$w(1),w(2),…,w(n)$。接下來有$n-1$行是道路的資料，每一行有兩個正整數$u$與$v$，代表有一條道路連接$u$與$v$。$n$不超過1e5，每個城鎮利益的絕對值不超過1e4。
輸出：最多可以獲得的總和利益。
範例一輸入：
5
-2 3 -1 3 -4
1 2
5 1
5 3
5 4
範例一輸出：
3
範例二輸入：
7
2 -1 4 -3 5 -3 2
1 2
2 3
4 3
5 4
5 6
7 6
範例二輸出：
7
範例一說明：選{2}或{4}都是3。
範例二說明：這是7個點排成一條路徑，選{1,2,3,4,5}，總和是7。
---
下面一題看起來也是類似的題目，他是Q-8-9的加權版本，但這一題比較困難。
---
##### P-8-13. 不同成本的購物中心 (@@)
有$n$個小村鎮以1 ~ $n$編號，這些村鎮以$n-1$條道路連接，每條道路都是雙向通行且連接兩個不同的村鎮，已知從任兩個村莊之間都可以經由這些道路通達，兩個村莊稱為鄰近的村莊，如果它們之間有一條道路直接相連。現在要選一些村莊成立服務中心，因為預算的關係無法每個村莊都成立一個服務中心，政府的政策決定：如果某個村莊沒有設服務中心，那麼他一定有一個鄰近的村莊有服務中心。也就是說，任何一個村莊最多只要經過一條道路就可以到達一個有設服務中心的村莊。每個村莊設立服務中心的成本不同，在編號$i$的村莊成立服務中心需要的成本是$w(i)$，我們希望以最少的總成本設置服務中心，請你計算最少的總成本。
Time limit: 2 秒
輸入格式：第一行是正整數$n$，$n>1$，村莊以1 ~ $n$編號。第二行有$n$個整數，依序是$w(1),w(2),…,w(n)$。接下來有$n-1$行是道路的資料，每一行有兩個正整數$u$與$v$，代表有一條道路連接$u$與$v$。$n$不超過1e5，每個村莊設置成本不超過1000。
輸出：需要成立服務中心的最少總成本。
範例一輸入：
5
2 4 1 3 7
1 2
5 1
5 3
5 4
範例一輸出：
6
範例二輸入：
7
1 3 3 1 2 2 1
1 2
2 3
4 3
5 4
5 6
7 6
範例二輸出：
3
範例一說明：設在{1,3,4}成本6。
範例二說明：這是7個點排成一條路徑，選{1,4,7}成本是3。
---
這一題是要計算minimum weight domination set，與最大獨立集類似的地方是：無加權時可以貪心，加權時必須用DP來解。最大獨立集的DP遞迴式比較容易，這一題的困難點並不是程式難寫或是需要什麼特別的資料結構與演算法，而是DP遞迴式很容易弄錯。子問題都定義在以任一點$r$為根的子樹的解，我們將子問題分成三類：
* $d1(r)$: 在$r$被挑選下的最佳解(domination set的最小權重)。
* $d01(r)$: 在$r$不被挑選但$r$已被管轄下的最佳解，也就是至少有一個$r$的孩子被挑選。
* $d00(r)$: 在$r$不被挑選且$r$不一定有沒有被管轄之下的最佳解。這個值未必是個合法的解，根$r$要靠上面的點管轄。
子問題的遞迴式如下($v$皆為對所有$r$的孩子)：
* $d1(r) = w(r) + \sum_{v\in child(r)} \min\{d00(v),d1(v)\}$。也就是對所有子樹的最小值加總後加上r的權重，因為 $d00(v)\le d01(v)$，所以只需要取$\min\{d00(v),d1(v)\}$。
* $d00(r) = \sum_{v\in child(r)} \min\{d1(v),d01(v)\}$
* $d01(r) = \sum_{v\in child(r)}\min\{d1(v),d01(v)\} + min\_diff$; 其中 $min\_diff = \max\{0, \min_{v\in child(r)}\{d1(v)-d01(v)\}\}$，也就是對所有孩子$v$找出$d1(v)-d01(v)$的最小值，這個值是正的就要加上，如果是負的就不加。遞迴式的意義在各孩子的最小合法解之總和，但是不能全部的孩子都沒有挑選。
程式並不特別難，一樣有top-down與bottom-up兩種寫法，以下是bottom-up的寫法，這裡我們以root開始走一個由上而下的BFS，走完之後把它反過來就是個Bottom-up 順序，然後根據此順序寫DP。top-down的寫法依然可能有遞迴過深的問題，請自行參考。
```python=
'''
P-8-13 min domination set of a tree
DP d1(r): min cost with root,
d01(r): without root but root is dominated
d00(r): without root and root is not necessarily dominated
d1(r)=w(r)+sum(min(d00(v),d1(v)): all child v of r), d00<=d01
d00(r)=sum(min(d1(v),d01(v)))
d01(r)=sum(min(d1(v),d01(v)))+ max(0,min(d1[v}-d01(v)))
not all d01
'''
n = int(input()); oo = 10**9
w = [0]+[int(x) for x in input().split()]
adj = [[] for i in range(n+1)]
for i in range(n-1):
u,v = [int(x) for x in input().split()]
adj[u].append(v)
adj[v].append(u)
# BFS to find a bottom-up seq
p = [0]*(n+1) # parent
que = [1]; head = 0 # root
while head < len(que):
v = que[head]; head += 1
for u in adj[v]:
if u != p[v]:
que.append(u)
p[u] = v
#
d1 = w
d00 = [0]*(n+1)
d01 = [oo]*(n+1)
for v in que[::-1]: # bottom-up
d01[v] = d00[v]+max(0,d01[v])
# contribue to parent
r = p[v]
d1[r] += min(d00[v],d1[v])
d00[r] += min(d1[v],d01[v])
d01[r] = min(d01[r], d1[v]-d01[v])
#
print(min(d1[1], d01[1]))
```
---
##### P-8-14. 血緣關係 (APCS201603)
小宇有一個大家族。有一天，他發現記錄整個家族成員和成員間血緣關係的家族族譜。小宇對於最遠的血緣關係 (我們稱之為"血緣距離") 有多遠感到很好奇。
上圖為家族的關係圖。0是7的孩子，1、2和3是0的孩子，4和5是1的孩子，6是3的孩子。我們可以輕易的發現最遠的親戚關係為4(或5)和6，他們的"血緣距離"是4 (4~1，1~0，0~3，3~6)。 我們將給你小宇家族的關係圖，請幫小宇找出最遠的"血緣距離"。你可以假設只有一個人是整個家族成員的祖先，而且沒有兩個成員有同樣的小孩。
Time limit: 2秒
輸入格式：第一行為一個正整數$n$ 代表成員的個數，每人以0 ~ $n-1$之間惟一的編號代表。接著的 $n-1$ 行，每行有兩個以一個空白隔開的整數$a$與$b$ ($0 \le a,b \le n-1$)，代表$b$是$a$的孩子。$n$不超過1e5。
輸出：輸出最遠"血緣距離"的答案。
範例一輸入：
8
0 1
0 2
0 3
7 0
1 4
1 5
3 6
範例一輸出：
4
範例二輸入：
4
0 1
0 2
2 3
範例二輸出：
3
範例一是題目中敘述的例子。
---
在一個圖中，最長的兩點最短路徑(距離)稱為直徑，直徑這個詞同時代表該路徑，也代表該路徑的長度。這個定義有點繞口，其實就像在平面幾何的圓中，直徑是圓上最遠的兩點的距離。如果對任意兩點$u$,$v$都求出兩點之間的最短距離$d(u,v)$，那麼
$diameter = \max\{d(u,v): \forall u,v \in V\}$。我們在前面的題目中已經知道，樹上求一點與其它點的距離可以在$O(n)$時間內完成，那麼直接依照定義求出所有點到所有點的距離然後計算直徑可以在$O(n^2)$時間完成。我們需要一個更有效率的解法。
這一題是無加權樹的直徑，算是樹的簡單DP中的經典題。先看用標準DP的寫法。因為直徑必然由某個葉節點往上走到某個點$r$之後，再從$r$的另外一個孩子一路往下走，退化的狀態是$r$只有一個孩子，那就只走到$r$為止，我們稱這樣的路徑為以$r$為最高點的路徑。
也可以換句話說，直徑一定是以某個$r$為最高點的最長路徑。我們只要對每個$r$，計算出以$r$為最高點的最長路徑，也就是$r$往下的兩條最長路徑，然後對所有的$r$取最大值就可以了，但是要小心的是，這兩條路徑必須經由兩個不同的孩子。
我們前面P-8-4學過樹中點的高度，事實上我們要找的就是$r$的兩個高度最高的孩子，把他們的高度相加再加2就是以$r$為最高點的最長路徑。
為了避免遞迴過深的問題，還是以Bottom-up DP來寫，首先是找出順序，這部分已說明多次。本題的重點在對於每一個節點，我們要找出高度最高的兩個孩子，這就像在一個數列中找出最大的兩個值一樣。如果用直接的寫法，通常需要用兩次迴圈，第一次找出最大值，第二次找出非最大值中的最大值；或者掃描一次但同時維護好第一名與第二名。這兩種寫法的時間複雜度是$O(n)$，因為對每一個點$r$，它需要的時間複雜度是$O(|child(r)|)$，而所有點的孩子數量總和不過是$O(n)$。但不管如何，這兩種寫法都有點囉嗦。
想想下面這招：假設數列是$S$，$pm$是prefix_max，則最大兩個元素之和其實就是
$\max\{S[i]+pm(i): \forall i\}$。
所以我們只需要一路掃描並維護好目前看到的最大值，每次將當下看到的值加上他之前的最大值相加即可。以下是範例程式，非常的簡潔漂亮。請留意，在prefix_max預設為0下，這個方法也適用只有一個孩子的情形。
```python=
# tree diameter, non-recursion
n = int(input())
p = [-1]*n # parent
deg = [0]*n # num of child
for i in range(n-1):
s,t = map(int,input().split())
p[t] = s
deg[s] += 1
#find a post order
pos = [x for x in range(n) if deg[x]==0]
head = 0
while head < len(pos):
v = pos[head]; head += 1
u = p[v]
if u<0: break # root
deg[u] -= 1
if deg[u]==0:
pos.append(u)
# bottom-up dp
h = [0]*n # height
d = 0 # diameter
for v in pos[:n-1]: # no root
r = p[v]
d = max(d, h[v]+1+h[r])
h[r] = max(h[r], h[v]+1)
print(d)
```
樹的直徑有另外一個演算法，但必須根據圖論的一個性質：「距離樹上任一點最遠的點，一定是某個直徑的端點」。這個性質的證明並不算難，但我們只簡要說明，有興趣的讀者自己去證明。若$v$是任一點，$u$是離$v$最遠的一點，而$D$是任一條直徑，則$v$到$u$的路徑與$D$必然相交；再則，$u$到$D$的兩端較遠者，必然也是直徑。
根據上述的性質，可以得到一個很簡單的線性時間演算法，我們稱為farthest of farthest演算法：
>挑選任一點$v$，找離它最遠的一點$u$，再找離$u$最遠的一點$s$，則$u$到$s$就是直徑。
以下是這樣的範例程式，我們以無根樹的方式用BFS來找距離最遠的點。因為要呼叫兩次，把BFS寫成函數，每次呼叫會算出離起點最遠的一點以及其距離。
```python=
# tree diameter, farthest of farthest
n = int(input())
adj = [[] for i in range(n)]
for i in range(n-1):
s,t = map(int,input().split())
adj[s].append(t)
adj[t].append(s)
# bfs to find distance
def bfs(s): # source s, return farthest
d = [-1]*n # -1 as uncomputed
que = [s]; head = 0
d[s] = 0
while head < len(que):
v = que[head]; head += 1
for u in adj[v]:
if d[u] < 0:
d[u] = d[v] + 1
que.append(u)
return que[-1],d[que[-1]]
#
v,_ = bfs(0) # find v farthest to 0
u,diameter = bfs(v) # find farthest to v
print(diameter)
```
下面一題是與直徑有關的習題，提示是：想想P-8-1的解答說明。此外，這一題是加權版，也就是邊是有不同長度的。
---
##### Q-8-15. 樹上一位不回家的推銷員
有一個推銷員要走訪$n$個城市。這些城市以$n-1$條道路連接，每條道路連接兩個不同的城市並且雙向可以通行，而且已知每一個城市都可以到達，不會有到達不了的狀況。輸入道路的資料，請你幫推銷員找出一個最短的路徑走訪所有的城市，推銷員可以從任何城市開始，也不必回到開始的城市，只要每個城市至少到一次就可以。
舉例來說，如上圖，有5個城市以4條道路連接，假設每條道路的長度都是1。最短的拜訪路徑是(1,0,4,2,4,3)，長度為5。
Time limit: 2秒
輸入格式：第一行是正整數$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
範例一輸出：
5
範例二輸入：
3
1 2 5
0 2 3
範例二輸出：
8
---
---
##### Q-8-16. 病毒演化 (APCS202007)
在資訊科學上，RNA病毒可以看成一個由A、U、G、C這四種字母構成的字串。病毒演化中，某些字元可能變異成其他字元，例如將AAUGG中的第3個位置的U換成C，則得到AACGG，變異可能發生在多個位置。有個實驗團隊取得了某種RNA病毒的數個RNA片段樣本，並且掌握到這些樣本演化的親緣關係，用
（樣本編號，親代編號，RNA字串）
的格式記錄，其中「樣本編號」與「親代編號」為兩個整數，若兩數字相同，則該樣本即為演化的源頭。例如，
（1, 1, AAAA）
（2, 1, GCAA）
表示樣本1的RNA字串為AAAA，樣本2的為GCAA，且樣本2是由樣本1在兩個位置發生變異演化而來，樣本1為演化的源頭。
然而，字串中每個位置的字元無法確定，實驗團隊以@來表示這些字元，換言之，@可能為A、U、G、C中任何一個。請注意，一個字串中可能有多個@，並非代表這些位置的字元是相同的。例如A@C@可能是任何第一個字元為A且第三個字元為C的字串，像是ACCU或AACC。團隊猜測演化過程發生的變異總數會盡可能的少。請你利用親緣關係，來計算最小的變異總數量。
Time limit: 1 秒
輸入格式：第一行有兩個正整數$n$與$m$，表示共有$n$個樣本，由 1 至 $n$ 編號；每個樣本之RNA字串長度均為$m$，其中$n \le 1000$且$m \le 80$。接下來$n$行，每行包含以空白間隔的兩個正整數$i$與$j$以及一個RNA字串$s_i$，對應一個樣本$（i, j, s_i）$，$s_i$由A、U、G、C與@五種字元所組成。若$i=j=1$，則該樣本即為演化的源頭，源頭以外的樣本皆恰有一個親代。
輸出：輸出最小可能的變異總數。
範例一輸入：
2 3
1 1 AAC
2 1 A@@
範例一輸出：
0
範例二輸入：
6 1
1 1 @
2 1 @
3 1 C
4 1 C
5 2 A
6 2 A
範例二輸出：
1
範例一說明：樣本2為AAC時，變異量為0。
範例二說明：我們以一樹狀結構表示此例的親緣關係：
將樣本1置換成C、樣本2置換成A，則只有在樣本1與2之間有一個變異，其它皆無變異，故答案是1。
---
Q-8-16提示：從範例二看到的第一件事是這些RNA是個樹狀結構，另外一個很重要的事情是：雖然每個點是個字串，但是字串的每個位置是獨立的，也就是所有字串的第1個字元，要算一個最小變異量；所有字串的第2個字元，要算一個最小變異量；對每一個字串位置$i$都要算一個最小變異量，最後的答案是把他們加起來。所以，我們只要會解字串長度$m=1$的狀況，最後套一個迴圈就好了。
如果沒有’@’，所有的變異都是確定的，只要把每個點與它的parent比較是否相等就好了，所以問題在如何決定’@’變異量。如果葉節點是’@’，我們可以讓它跟它的parent相同，這顯然不會有變異量，也就是說是’@’的葉子根本可以無視它。為了計算方便，我們先將AUCG轉換為數字0 ~ 3，以DP的觀點，對於每個節點$v$，我們算四個成本$cost[v][i]$, $i$從0到3，分別代表如果parent的字元是$i$的時候$v$點以下子樹的總成本，然後去建構出遞迴式。
**End of Chapter 8**
Sign in with Wallet
Connect another wallet