|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|1 초||512 MB||63||53||50||84.746%|
The famous Jurassic park biologist Dean O’Saur has discovered new samples of what he expects to be the DNA of a dinosaur. With the help of his assistant Petra Dactil, he managed to sequence the samples, and now they are ready for analysis. Dean thinks this dinosaur was affected with a particular disease mutating the DNA of some cells.
To verify his theory, he needs to compute the most likely evolutionary tree from the samples, where the nodes are the samples of DNA. Because there is no temporal data of the DNA samples, he is not concerned where the root of the tree is.
Dean considers the most likely evolutionary tree, the tree with smallest unlikeliness: the unlikeliness of a tree is defined as the sum of the weights of all edges, where the weight of an edge is the number of positions at which the two DNA strings are different.
As a world expert in data trees, he asks you to reconstruct the most likely evolutionary tree.
In the first sample, the optimal tree is
AA - AT - TT - TC . The unlikeliness of the edge between
AT edge is 1, because the strings
AT differ in exactly 1 position. The weights of the other two edges are also 1, so that the unlikeliness of the entire tree is 3. Since there is no tree of unlikeliness less than 3, the minimal unlikeliness of an evolutionary tree for this case is 3.
4 2 AA AT TT TC
3 0 1 1 2 2 3
4 1 A A G T
2 0 1 0 2 0 3
5 6 GAACAG AAAAAA AACATA GAAAAG ATAAAT
7 0 3 1 2 1 3 1 4