결측값 대체

Leila는 세균의 진화를 연구하는 생물정보학자이다. 특별한 종류의 세균을 대상으로 한 실험에서 그녀는 세균 하나에서 시작해 그것을 배양 접시에 놓고 세균의 분열을 관찰하여 k개의 세균으로 이루어진 개체군을 얻었다. 그 과정에서 그녀는 세균 사이의 진화적 관계를 세심하게 기록했다. 정확히 말해, 각 세균에 대해 그 부모 세균을 기록했다.

다음 단계에서 그녀는 NGS 기술로 최종 개체군의 k개 세균에서 DNA 서열을 추출했다. 각 DNA 서열은 알파벳 집합 {A, T, C, G}의 문자로 이루어진 길이 m의 문자열로 표현된다.

NGS 기술에는 결점이 하나 있다. 결측값을 많이 만들어낸다는 것이다. 그래서 추출된 서열에는 '?'로 표시된 미지의 문자가 많이 있다. Leila는 세균 사이의 진화적 관계를 고려하여 결측값을 대체하려고 한다. 가능한 모든 대체 중에서 그녀는 진화적 관점에서 최소 비용의 대체를 찾고자 한다.

문제는 다음과 같이 정의된다. 뿌리 있는 트리 T가 주어지고, T의 각 잎 v에 대해 문자 집합 {A, T, C, G, ?}의 문자로 이루어진 길이 m의 문자열 bv가 주어진다. 또한 전이 비용 행렬 ∆가 주어지는데, ∆(x, y) (x, y ∈ {A, T, C, G})는 부모에서 자식으로 갈 때 x 문자에서 y 문자로의 전이 비용을 나타낸다.

실현 가능한 대체는 각 정점 u에 문자 집합 {A, T, C, G}의 문자로 이루어진 길이 m의 문자열 su를 부여하는 것으로, T의 각 잎 v에 대해 sv는 bv에서 '?' 문자를 제외하고 bv와 같다. 대체의 진화 비용은 모든 간선의 진화 비용의 합으로 정의된다. 부모 u와 자식 w 사이 간선의 진화 비용은 Σmi=1 ∆(su[i], sw[i])로 정의되는데, 여기서 su[i]는 su의 i번째 문자이다.

Leila는 T에 대한 실현 가능한 대체 중에서 모든 실현 가능한 대체 가운데 최소 진화 비용을 가지는 것을 찾고자 한다. 트리 T, 전이 비용 행렬 ∆, 각 잎 v에 대한 문자열 bv가 주어진다. 실현 가능한 대체의 최소 진화 비용을 계산하는 프로그램을 작성해야 한다.

입력의 첫째 줄에는 T의 정점 수를 나타내는 정수 n (2 ⩽ n ⩽ 10, 000)이 주어진다. T의 정점은 1부터 n까지 번호가 매겨진다. 트리의 뿌리는 1번이다. 뿌리는 자식이 하나뿐이더라도 잎으로 여기지 않는다. 다음 n − 1개 줄은 T의 간선을 설명한다. 각 줄에는 간선의 두 끝점이 공백으로 구분되어 주어진다. 그다음 네 줄에 진화 비용 행렬 ∆가 주어지는데, 각 줄은 ∆의 한 행이다. ∆의 행(부모에 대응)과 열(자식에 대응)은 각각 문자 A, T, C, G를 나타내도록 정렬되어 있다. ∆의 모든 원소는 106 이하의 음이 아닌 정수이다. 그다음 줄에는 잎의 수 k가 주어진다. 마지막으로 각 잎 v(그 번호)와 크기 m (1 ≤ m ≤ 200)의 문자열 bv가 한 줄에 하나씩 주어진다.

실현 가능한 대체의 최소 진화 비용을 한 줄에 출력한다.