Problem
Caiman은 그가 도시의 이상한 지역에 있다는 특이한 꿈을 꿉니다. 이 영역은 트리 그래프로 나타낼 수 있으며 정점은 교차로이고 가장자리는 이러한 교차로를 연결하는 양방향 도로입니다. 총 n개의 교차로가 있으며 각각은 0에서 n-1까지 고유한 번호를 가집니다.
그러나이 꿈에서 모든 것이 그렇게 나쁘지는 않습니다. 숫자 u와 v가있는 교차로 사이의 모든 도로에는 C
u,v 만두가 있기 때문입니다! 카이만은 만두를 무척 좋아해서 최대한 먹고 싶은데 문제가 하나 있습니다. 어떤 교차로든 k번 이상 방문하면 사악한 만두 괴물의 공격을 받게 됩니다.
이것은 꿈이지만 각 길의 만두는 한 번만 먹을 수 있지만 길을 여러 번 걷는 것을 방해하는 것은 없습니다. 또한 케이맨은 도로에서 멈추지 않습니다. 즉, 한 교차로에서 다른 교차로로 이동하기 시작하면 반드시 다음 교차로까지 끝까지 갈 것입니다.
꿈의 시작에서 카이만은 교차로 0번에 있습니다. 사악한 만두 괴물의 공격을 받지 않고 먹을 수 있는 최대 만두 수를 결정하도록 도와주세요.
입력:
첫 번째 줄은 두 개의 정수 n과 k를 포함합니다(3 ≤ n ≤ 10
5; 1 ≤ k ≤ 10
5) &mdash ; 교차로의 수와 각 교차로의 최대 방문 횟수.
다음 n - 1 행에는 3개의 정수 u, v 및 C
u,v(0 ≤ u, v
u,v< /sub > ≤ 10000), 이는 숫자 u와 v가 있는 교차로가 Cu,v 만두가 있는 도로로 연결됨을 의미합니다.
교차로와 도로가 나무를 이루는 것이 보장됩니다.
출력:
하나의 정수를 출력하세요 - 카이만이 먹을 수 있는 만두의 최대 개수입니다.
예:
<몸>
| 입력 |
출력 |
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
1952년 21월
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 |
설명:
첫 번째 예에서는 다음 순서로 교차로를 방문해야 합니다. ;2, 7, ?2, ?8. 그런 다음 총 1+2+2+1+3+3+3 = 만두 15개를 먹게 됩니다.
교차로는 3회 이상 방문하지 않습니다.