Árbol filogenético P33979

Un árbol filogenético muestra las relaciones evolutivas entre n especies. En nuestro caso particular, suponemos que es un árbol binario cuyos nodos internos son especies ya extintas, y cuyas hojas son especies que aún viven.

Estáis estudiando la evolución de un gen concreto en las especies representadas en un árbol filogenético. Sabéis que el gen tiene g variantes posibles, y conocéis la variante concreta para las especies vivas, pero no para las extintas. Vuestro objetivo es asignar una variante del gen a cada especie extinta de manera que el árbol filogenético resultante tenga la máxima parsimonia posible. En este problema, definimos la parsimonia como el número de especies que tienen la misma variante del gen que su antecesor inmediatamente superior.

Considerad estos dos árboles filogenéticos,

los cuales se corresponden al Ejemplo 2. En ambos casos, asignando un 1 a todos los nodos internos se obtiene la máxima parsimonia posible, la cual es 2 y 5, respectivamente.

Entrada

La entrada consiste en diversos casos, cada uno de los cuales empieza con n y g, seguidas de la información de cada especie i, en orden de la 1 a la n. Si la especie está extinta, tenemos una ‘E’ seguida de dos enteros a_i y b_i con las dos especies sucesoras de la especie i. Si la especie aún está viva, tenemos una ‘V’ seguida de un entero x_i que indica la variante del gen para i. Podéis suponer n ≥ 1, g ≥ 2, i < a_i < b_i ≤ n, y 1 ≤ x_i ≤ g. También podéis suponer que la entrada se corresponde con un árbol correcto, en particular que n es impar, y que ninguna especie tiene más de un antecesor.

Salida

Por cada caso, escribid la máxima parsimonia posible.

Puntuación

• test-1:  ‍ Resolver varias entradas donde n < 16 y g = 2.  ‍40 Puntos ‍

• test-2:  ‍ Resolver varias entradas donde n < 500 y g = 2.  ‍20 Puntos ‍

• test-3:  ‍ Resolver varias entradas donde n < 500 y g ≤ 40.  ‍20 Puntos ‍

• test-4:  ‍ Resolver varias entradas donde n < 2000 y g ≤ 500.  ‍20 Puntos ‍