Problem
Caiman tem um sonho inusitado, em que está em uma parte estranha da cidade. Esta área pode ser representada como um gráfico de árvore, onde os vértices são interseções e as arestas são vias de mão dupla que conectam essas interseções. Existem n interseções no total e cada uma tem seu próprio número de 0 a n-1.
Mas nem tudo é tão ruim neste sonho, porque em todas as estradas entre os cruzamentos com os números u e v existem bolinhos C
u,v! Caiman adora bolinhos de massa, então ele quer comer o máximo possível, mas há um problema - se ele visitar qualquer encruzilhada mais de k vezes, ele será atacado por um monstro maligno de bolinho de massa.
Embora seja um sonho, os bolinhos de cada estrada só podem ser comidos uma vez, embora nada o impeça de caminhar várias vezes pelas estradas. Também Cayman não para nas estradas. Ou seja, se ele começar a se mover de um cruzamento para outro, com certeza irá até o próximo cruzamento.
No início do sonho, Caiman está na encruzilhada número 0. Ajude-o a determinar o número máximo de bolinhos que ele pode comer sem ser atacado pelo malvado monstro dos bolinhos.
Entrada:
A primeira linha contém dois inteiros n e k (3 ≤ n ≤ 10
5; 1 ≤ k ≤ 10
5) &mdash ; o número de cruzamentos e o número máximo de visitas a cada um dos cruzamentos.
As próximas n - 1 linhas contêm três inteiros u, v e C
u,v (0 ≤ u, v ≤ n - 1; 0 ≤ C
u,v< /sub > ≤ 10000), o que significa que as interseções com os números u e v são conectadas por uma estrada com bolinhos Cu,v.
É garantido que cruzamentos e estradas formam uma árvore.
Saída:
Imprima um único inteiro - o número máximo de bolinhos que Caiman pode comer.
Exemplos:
| Entrada |
Saída |
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 |
Explicação:
No primeiro exemplo, você precisa visitar as interseções na seguinte ordem: 0, 1, 5, 1, 3, 1, 0, 2, 6,&thinsp ;2, 7, ?2, ?8. Então ele vai comer um total de 1+2+2+1+3+3+3 = 15 bolinhos.
Observe que nenhuma interseção é visitada mais de 3 vezes.