Problem
Caiman ha un sogno insolito, che si trova in una strana parte della città. Quest'area può essere rappresentata come un grafico ad albero, dove i vertici sono le intersezioni ei bordi sono strade a doppio senso che collegano queste intersezioni. Ci sono n incroci in totale e ognuno ha il proprio numero da 0 a n-1.
Ma non tutto è così brutto in questo sogno, perché su ogni strada tra gli incroci con i numeri u e v ci sono gnocchi C
u,v! Caiman ama molto gli gnocchi, quindi vuole mangiare il più possibile, ma c'è un problema: se visita un incrocio più di k volte, verrà attaccato da un malvagio mostro di gnocchi.
Anche se questo è un sogno, gli gnocchi su ogni strada possono essere mangiati solo una volta, anche se nulla ti impedisce di camminare più volte lungo le strade. Anche Cayman non si ferma sulle strade. Cioè, se inizia a spostarsi da un incrocio all'altro, andrà sicuramente fino all'incrocio successivo.
All'inizio del sogno, Caiman si trova all'incrocio numero 0. Aiutalo a determinare il numero massimo di ravioli che può mangiare senza essere attaccato dal malvagio mostro dei ravioli.
Inserimento:
La prima riga contiene due numeri interi n e k (3 ≤ n ≤ 10
5; 1 ≤ k ≤ 10
5) &mdash ; il numero di incroci e il numero massimo di visite a ciascuno degli incroci.
Le successive n - 1 righe contengono tre numeri interi u, v e C
u,v (0 ≤ u, v ≤ n - 1; 0 ≤ C
u,v< /sub > ≤ 10000), nel senso che gli incroci con i numeri u e v sono collegati da una strada con Cu,v gnocchi.
È garantito che gli incroci e le strade formino un albero.
Uscita:
Stampa un singolo numero intero: il numero massimo di gnocchi che Caiman può mangiare.
Esempi:
| Input |
Uscita |
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 |
Spiegazione:
Nel primo esempio, devi visitare gli incroci nel seguente ordine: 0, 1, 5, 1, 3, 1, 0, 2, 6,&thinsp ;2, 7, ?2, ?8. Quindi mangerà un totale di 1+2+2+1+3+3+3 = 15 gnocchi.
Tieni presente che nessun incrocio viene visitato più di 3 volte.