Problem
Caiman fait un rêve inhabituel, qu'il se trouve dans une partie étrange de la ville. Cette zone peut être représentée sous la forme d'un graphique arborescent, où les sommets sont des intersections et les bords sont des routes à double sens qui relient ces intersections. Il y a n intersections au total et chacune a son propre numéro de 0 à n-1.
Mais tout n'est pas si mauvais dans ce rêve, car sur chaque route entre les intersections avec les numéros u et v, il y a des boulettes C
u,v ! Caiman aime beaucoup les boulettes, donc il veut manger autant que possible, mais il y a un problème - s'il visite un carrefour plus de k fois, il sera attaqué par un monstre boulette maléfique.
Bien que ce soit un rêve, les boulettes sur chaque route ne peuvent être mangées qu'une seule fois, bien que rien ne vous empêche de marcher plusieurs fois le long des routes. Aussi Cayman ne s'arrête pas sur les routes. Autrement dit, s'il commence à se déplacer d'une intersection à une autre, il ira certainement jusqu'à l'intersection suivante.
Au début du rêve, Caïman se trouve au carrefour numéro 0. Aidez-le à déterminer le nombre maximum de boulettes qu'il peut manger sans être attaqué par le méchant monstre boulette.
Saisie :
La première ligne contient deux entiers n et k (3 ≤ n ≤ 10
5; 1 ≤ k ≤ 10
5) &mdash ; le nombre d'intersections et le nombre maximum de visites à chacune des intersections.
Les n - 1 lignes suivantes contiennent trois entiers u, v et C
u,v (0 ≤ u, v ≤ n - 1; 0 ≤ C
u,v< /sub > ≤ 10000), ce qui signifie que les intersections avec les numéros u et v sont reliées par une route avec des boulettes Cu,v.
Il est garanti que les intersections et les routes forment un arbre.
Sortie :
Imprimer un seul entier - le nombre maximum de raviolis que Caiman peut manger.
Exemples :
| Entrée |
Sortie |
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 |
Explication :
Dans le premier exemple, vous devez visiter les intersections dans l'ordre suivant : 0, 1, 5, 1, 3, 1, 0, 2, 6,&thinsp ;2,&minsp;7, ?2, ?8. Ensuite, il mangera un total de 1+2+2+1+3+3+3 = 15 boulettes.
Notez qu'aucune intersection n'est visitée plus de 3 fois.