# APCS實作題2020年7月第4題：病毒演化
> 日期：2024年8月29日
> 作者：王一哲
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=f582)
## 題目
### 問題描述
科學家發現了 $n$ 種病毒，編號分別是 $1$ 到 $n$，已知每一種病毒可以用一個RNA 序列來表達，RNA序列是一個長度為 $m$ 的字串，其中包含 A、U、C、G、@ 等字元，其中 @ 為科學家沒觀察清楚的位置，可能為 A、U、C、G 其中任何一種。
科學家也研究出了這些病毒的演化關係，除了一個最原始的病毒以外，每一種病毒都是從另一個病毒演化而來的，這些病毒會構成一個樹狀結構的病毒族譜(如圖)。
<br />
<img height="80%" width="80%" src="https://zerojudge.tw/ShowImage?id=1671" style="display: block; margin-left: auto; margin-right: auto;"/>
<br /><br />
兩個 RNA 序列的的距離定義為它們的漢明距離，也就是相異的位數個數。更具體的說，對於兩個長度都是 $m$ 的 RNA 序列 $a, b$，它們的漢明距離就是有幾個位置 $i$ 滿足 $a_i \neq b_i$。你想知道目前的病毒族譜的每一個 RNA 序列中的 @ 字元的填入 A、U、C、G 中的其中一個字元後，每一個病毒與它演化來源的病毒的距離總合最小值是多少？
### 輸入說明
第一行包含兩個正整數 $n, m~ (1 \leq n \leq 1000,~ 1 \leq m \leq 80)$。
接下來 $n$ 行，每行表示一種病毒，包含兩個整數 $i, j$ 與一個字串 $s$，表示編號 $i$ 的病毒是從編號 $j$ 的病毒演化而來的，且編號 $i$ 的病毒的 RNA 序列為 $s$。若編號 $i$ 的病毒是最原始的病毒，則 $j = i$，保證這樣的病毒只會有一個。
配分
- 20分：RNA 序列中沒有 @，每個病毒都滿足 $j < i$。
- 40分：每個病毒都滿足 $j < i$。
- 40分：同原題目限制。
<br />
### 輸出說明
輸出每種病毒到它演化來源的病毒的距離總和最小值。
<br />
### 範例輸入1
```
2 3
1 1 AAC
2 1 A@@
```
### 範例輸出1
```
0
```
<br />
### 範例輸入2
```
6 1
1 1 @
2 1 @
3 1 C
4 1 C
5 2 A
6 2 A
```
### 範例輸出2
```
1
```
<br />
## Python 程式碼
費時最久約為 0.3 s，使用記憶體最多約為 4.6 MB，通過測試。
```python=
"""
cost[v][i] 這個節點 v 的父節點是字元 i 時，v 節點以下子樹的總變異量
狀況1，rna[v] 是 AUCG，v 節點以下子樹的總變異量可確定
(1) 先加上 v 之下所有子樹的總變異量，可以直接結算，加到儲存答案的全域變數 total
(2) 再加上 v 與 par[v] 的變異量，如果兩者相等為 0，否則為 1
狀況2，rna[v] 是 @
(1) 先計算 v 之下所有子樹對應到 AUCG 的總變異量，取其中的最小值為 mcost
(2) 如果 par[v] 對應的字元可以使變異量為 mcost，則 cost[v][i] = mcost
(3) 如果 par[v] 對應的字元無法使變異量為 mcost
(a) 如果要達成 mcost @ 對應的字元不等於 par[v]，變異量為 mcost+1
(b) 如果 @ 對應的字元等於 par[v]，變異量至少為 mcost+1
要達到最小變異量，取 (a)。
"""
n, m = map(int, input().split()) # 節點（病毒）數量 n，RNA 序列長度 m
deg = [0]*(n+1) # 各節點對應的子節點數量，因為編號為 1 ~ n，故長度取 n+1
par = [0]*(n+1) # 各節點對應的父節點編號，因為編號為 1 ~ n，故長度取 n+1
rna = [[0]*m for _ in range(n+1)] # 各節點對應的字串（RNA 序列）
cov = {'A': 0, 'U': 1, 'C': 2, 'G': 3, '@': 4} # 轉換字元、整數的對照表
for i in range(1, n+1): # 讀取 n 行資料
a, b, s = input().split() # 子節點 a，父節點 b，字串 s
a = int(a); b = int(b) # 轉成整數
if a != b: # 不是根節點（最原始的病毒）
par[a] = b # 節點 a 的父節點是 b
deg[b] += 1 # 節點 b 的子節點數量加 1
rna[a] = [cov[c] for c in s] # 節點 a 對應的字串為 s
""" 找出 bottom-up 序列 """
seq = [i for i in range(1, n+1) if deg[i] == 0] # 放入葉節點
head = 0 # 從 seq 讀取資料的索引值
while len(seq) < n: # 結束時 seq 長度為 n
v = seq[head]; head += 1 # 讀取節點 v，head 加 1
p = par[v] # 讀取節點 v 的父節點 p
if p == 0: break # 遇到根節點 break
deg[p] -= 1 # p 的子節點數減 1
if deg[p] == 0: seq.append(p) # 如果 p 已經沒有子節點，將 p 加入 seq
# 結束 while 迴圈
# 判斷是否為不合規則的狀況，但是在 ZeroJudge 上不會遇到
if len(seq) != n or par[seq[-1]] != 0: # seq 數量不等於 n 或最後一項不是根節點
print("wrong case"); print(seq)
""" 找完序列 """
""" 主要的解題過程 """
total = 0 # 答案，總變異量
for i in range(m): # RNA 序列長度為 m，要跑 m 次
cost = [[0]*4 for _ in range(n+1)] # cost[v][i] 這個節點 v 的父節點是字元 i 時，v 節點以下子樹的總變異量
for v in seq: # 依序由 seq 讀取要測試的節點 v
ch = rna[v][i] # 節點 v 的第 i 個字元
if ch < 4: # 如果是 AUCG
total += cost[v][ch] # 結算 cost[v][ch]
for j in range(4): # 處理 v 與 par[v] 的變異量
if j != ch: cost[par[v]][j] += 1 # 不相等，加 1
else: # 如果是 @
mcost = min(cost[v]) # 取出 v 的最小變異量
total += mcost # 結算 mcost
for j in range(4): # 處理 v 與 par[v] 的變異量
if cost[v][j] != mcost: # 如果要達成 mcost @ 對應的字元不等於 par[v]，加 1
cost[par[v]][j] += 1
""" 結束主要的解題過程 """
print(total) # 印出答案
```
<br /><br />
## C++ 程式碼
費時最久約為 6 ms，使用記憶體最多約為 688 kB，通過測試。
```cpp=
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0); // 加速
int n, m; cin >> n >> m; // 節點（病毒）數量 n，RNA 序列長度 m
int a, b; string s; // 子節點 a，父節點 b，字串 s
int par[n+1] = {0}, deg[n+1] = {0}; // par 各節點對應的父節點編號，deg 各節點對應的子節點數量，因為編號為 1 ~ n，故長度取 n+1
int rna[n+1][m] = {{0}}; // 各節點對應的字串（RNA 序列）
map<char, int> cov = {{'A', 0}, {'U', 1}, {'C', 2}, {'G', 3}, {'@', 4}}; // 轉換字元、整數的對照表
for(int i=1; i<=n; i++) { // 讀取 n 行資料
cin >> a >> b >> s; // 子節點 a，父節點 b，字串 s
if (a != b) { // 不是根節點（最原始的病毒）
par[a] = b; // 節點 a 的父節點是 b
deg[b]++; // 節點 b 的子節點數量加 1
}
for(int j=0; j<m; j++) rna[a][j] = cov[s[j]]; // 節點 a 對應的字串為 s
}
/* 找出 bottom-up 序列 */
vector<int> seq; // 序列
for(int i=1; i<=n; i++) if (deg[i] == 0) seq.push_back(i); // 放入葉節點
int head = 0; // 從 seq 讀取資料的索引值
while((int)seq.size() < n) { // 結束時 seq 長度為 n
int v = seq[head]; head++; // 讀取節點 v，head 加 1
int p = par[v]; // 讀取節點 v 的父節點 p
if (p == 0) break; // 遇到根節點 break
deg[p]--; // p 的子節點數減 1
if (deg[p] == 0) seq.push_back(p); // 如果 p 已經沒有子節點，將 p 加入 seq
}
/* 主要的解題過程 */
int total = 0; // 答案，總變異量
for(int i=0; i<m; i++) { // RNA 序列長度為 m，要跑 m 次
int cost[n+1][4] = {{0}}; // cost[v][i] 這個節點 v 的父節點是字元 i 時，v 節點以下子樹的總變異量
for(int v : seq) { // 依序由 seq 讀取要測試的節點 v
int ch = rna[v][i]; // 節點 v 的第 i 個字元
if (ch < 4) { // 如果是 AUCG
total += cost[v][ch]; // 結算 cost[v][ch]
for(int j=0; j<4; j++) // 處理 v 與 par[v] 的變異量
if (j != ch) cost[par[v]][j]++; // 不相等，加 1
} else { // 如果是 @
int mcost = *min_element(cost[v], cost[v]+4); // 取出 v 的最小變異量
total += mcost; // 結算 mcost
for(int j=0; j<4; j++) { // 處理 v 與 par[v] 的變異量
if (cost[v][j] != mcost) // 如果要達成 mcost @ 對應的字元不等於 par[v]，加 1
cost[par[v]][j]++;
}
}
}
}
cout << total << "\n"; // 印出答案
return 0;
}
```
<br /><br />
## 參考資料
1. 吳邦一教授的 APCS 解題影片〈[PyAp45 Python APCS 題解：病毒演化(AP202007_4), ZeroJudge f582](https://youtu.be/9d0eD7fODHg?si=vpRa4u8un_G39l_W)〉
2. 吳邦一教授的 APCS 解題講義〈[AP325-Python 第8章 樹上演算法 (III)](https://hackmd.io/@bangyewu/Hy2kbYLI6/%2FE-EfMMi1Tw6DeoIY-WJzeQ#Q-8-16-%E7%97%85%E6%AF%92%E6%BC%94%E5%8C%96-APCS202007)〉
---
###### tags:`APCS`、`Python`、`C++`
Sign in with Wallet
Connect another wallet