病毒演化 (APCS 2020-07 高級)

科學家發現了 \(n\) 種病毒，編號分別為 \(1\) 到 \(n\)。每一種病毒都可以用一個 RNA 序列表示；RNA 序列是一個長度為 \(m\) 的字串，其中只包含 A、U、C、G、@ 等字元。@ 表示科學家沒有觀察清楚的位置，可能是 A、U、C、G 中的任何一種。

科學家也研究出了這些病毒的演化關係。除了一個最原始的病毒以外，每一種病毒都是從另一種病毒演化而來，因此這些病毒會構成一棵樹狀的病毒族譜。

兩個 RNA 序列的距離定義為它們的漢明距離，也就是兩個序列中不同字元的位置數量。更具體地說，對於兩個長度皆為 \(m\) 的 RNA 序列 \(a\)、\(b\)，它們的漢明距離為滿足 \(a_i\ne b_i\) 的位置 \(i\) 的數量。

請將每個 RNA 序列中的所有 @ 分別替換成 A、U、C、G 中的一個字元，使每一種病毒與它演化來源的病毒之間的距離總和最小，並輸出這個最小值。

輸入格式

第一行包含兩個正整數 \(n\)、\(m\)。

接下來 \(n\) 行，每行包含兩個整數 \(i\)、\(j\) 與一個字串 \(s\)，表示編號 \(i\) 的病毒由編號 \(j\) 的病毒演化而來，且編號 \(i\) 的病毒之 RNA 序列為 \(s\)。

若編號 \(i\) 的病毒是最原始的病毒，則 \(j=i\)。保證這樣的病毒恰有一個，且輸入描述的演化關係構成一棵樹。每個病毒編號都恰好出現一次。

輸出格式

輸出一個整數，代表所有病毒與其演化來源病毒之間的距離總和最小值。最原始的病毒不產生距離。

限制

• \(1\le n\le1000\)
• \(1\le m\le80\)
• \(s\) 的長度恰為 \(m\)，且只包含 A、U、C、G、@
• 記憶體限制為 256 MB
• 每筆測試資料的執行時間限制為 0.5 秒

子題

正式評測共有 20 筆計分測試資料，每筆 5 分。

範例輸入 1

2 3
1 1 AAC
2 1 A@@

範例輸出 1

0

範例輸入 2

6 1
1 1 @
2 1 @
3 1 C
4 1 C
5 2 A
6 2 A

範例輸出 2

1

題目來源

APCS 2020 年 7 月程式實作題第 4 題「病毒演化」，亦收錄於 ZeroJudge f582。