Árbol Verde-Naranja

Points: 100 (partial)

Time limit: 1.0s

Python 2 4.0s

Memory limit: 64M

Python 2 128M

Authors:

luismo, leocar, leo, eliogovea

Problem types

Allowed languages

Ada, BrainF***, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Prolog, Python, Swift, VB

Le será dado un árbol de $N$ ~N~ $(1 \leq N \leq 1000)$ ~(1 \leq N \leq 1000)~ nodos, donde cada arista está coloreada de verde o naranja. Sea $K$ ~K~ un entero entre 2 y $N$ ~N~. Cual es la mayor cantidad de aristas verdes en un subárbol de exactamente $K$ ~K~ nodos?

Especificación de Entrada

En la primera line dos valores enteros $N$ ~N~ y $K$ ~K~. Las siguientes $N - 1$ ~N - 1~ líneas contienen tres enteros separados por espacios A, B y C, $(1 \leq A,B \leq N$ ~(1 \leq A,B \leq N~), $C (0 \leq C \leq 1)$ ~C (0 \leq C \leq 1)~, donde $A$ ~A~ y $B$ ~B~ representan los nodos unidos por la arista actual y C el valor del color de la arista (0 - Naranja, 1 - Verde).

Especificación de Salida

Imprimir la mayor cantidad de aristas verdes que pueden hallarse en un subárbol de exactamente K nodos $(1 \leq K \leq N)$ ~(1 \leq K \leq N)~.

Ejemplo de Entrada

Ejemplo de Salida

Comments

-7

Primervirgen commented on Nov. 3, 2019, 3:20 p.m.

Para la resolución de este ejercicio q algoritmo de árboles utilizamos? Un DFS o MST?

This comment is hidden due to too much negative feedback. Show it anyway.

13

Leonardo commented on Aug. 26, 2019, 1:27 a.m.

Es un tipo de dp on tree,busca la solucion para un problema similar que es famoso se llama Baricades,esta explicado en el libro Looking for a challenge

4

dcq commented on Aug. 24, 2019, 10:07 p.m.

Alguna sugerencia de alguien para hacer este ejercicio???