時間限制 500 ms ・ 記憶體限制 256 MB
題目描述
n 種病毒構成一棵有根演化樹，每種病毒都有長度 m 的 RNA 字串。字元是 A、U、C、G 或 @；每個 @ 可以獨立補成四種字母之一。兩個 RNA 的距離是同一位置字元不同的個數。請替全部 @ 選字，使每個非根病毒與其來源病毒的距離加總最小。
輸入格式
第一行為 n、m，1 ≤ n ≤ 1000，1 ≤ m ≤ 80。接著 n 行各為 i、j、s，表示病毒 i 由病毒 j 演化而來，RNA 為 s，病毒編號為 1 至 n。唯一的根以 i=j 表示，其餘關係形成樹。輸入行不保證依編號或祖先順序排列。
輸出格式
輸出可能的最小距離總和。
範例測資
範例輸入 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
請先登入後再提交程式碼
討論與題解
載入討論區…