Problem
Caiman tiene un sueño inusual, que está en una parte extraña de la ciudad. Esta área se puede representar como un gráfico de árbol, donde los vértices son intersecciones y los bordes son caminos de doble sentido que conectan estas intersecciones. Hay n intersecciones en total y cada una tiene su propio número de 0 a n-1.
Pero no todo es tan malo en este sueño, porque en cada camino entre las intersecciones con los números u y v hay albóndigas C
u,v! A Caiman le encantan las albóndigas, por lo que quiere comer tanto como sea posible, pero hay un problema: si visita cualquier cruce de caminos más de k veces, será atacado por un malvado monstruo de albóndigas.
Aunque esto es un sueño, las albóndigas de cada camino solo se pueden comer una vez, aunque nada impide caminar por los caminos varias veces. También Cayman no se detiene en las carreteras. Es decir, si comienza a moverse de una intersección a otra, definitivamente irá hasta la siguiente intersección.
Al comienzo del sueño, Caiman se encuentra en la encrucijada número 0. Ayúdalo a determinar el número máximo de albóndigas que puede comer sin ser atacado por el malvado monstruo de las albóndigas.
Entrada:
La primera línea contiene dos números enteros n y k (3 ≤ n ≤ 10
5; 1 ≤ k ≤ 10
5) &mdash ; el número de intersecciones y el número máximo de visitas a cada una de las intersecciones.
Las siguientes n - 1 líneas contienen tres enteros u, v y C
u,v (0 ≤ u, v ≤ n - 1; 0 ≤ C
u,v< /sub > ≤ 10000), lo que significa que las intersecciones con los números u y v están conectadas por un camino con Cu,v dumplings.
Se garantiza que las intersecciones y caminos forman un árbol.
Salida:
Imprime un solo número entero: el número máximo de albóndigas que Caiman puede comer.
Ejemplos:
| Entrada |
Salida |
9 3
0 1 1
0 2 1
1 3 2
1 4 2
1 5 2
2 6 3
2 7 3
2 8 3
| 15 |
9 5
0 1 1
0 2 1
1 3 2
1 4 2
1 5 2
2 6 3
2 7 3
2 8 3
| 17 |
11 6
1 0 7932
21 1952
3 2 2227
4 0 9112
5 4 6067
6 0 6786
7 6 3883
8 4 7137
9 1 2796
10 5 6200
| 54092 |
Explicación:
En el primer ejemplo, debe visitar las intersecciones en el siguiente orden: 0, 1, 5, 1, 3, 1, 0, 2, 6,&thinsp ;2, 7, ?2, ?8. Luego comerá un total de 1+2+2+1+3+3+3 = 15 albóndigas.
Tenga en cuenta que ninguna intersección se visita más de 3 veces.