Problem
Caiman có một giấc mơ khác thường, rằng anh ta đang ở một khu vực xa lạ của thành phố. Khu vực này có thể được biểu diễn dưới dạng biểu đồ cây, trong đó các đỉnh là các giao lộ và các cạnh là các đường hai chiều nối các giao lộ này. Có tổng cộng n giao điểm và mỗi giao điểm có số riêng từ 0 đến n-1.
Nhưng không phải mọi thứ trong giấc mơ này đều tồi tệ như vậy, bởi vì trên mọi con đường giữa các ngã tư có số u và v đều có bánh bao C
u,v! Caiman rất thích bánh bao, vì vậy anh ấy muốn ăn càng nhiều càng tốt, nhưng có một vấn đề - nếu anh ấy đi qua bất kỳ ngã tư nào hơn k lần, anh ấy sẽ bị tấn công bởi một con quái vật bánh bao độc ác.
Mặc dù đây là một giấc mơ, bánh bao trên mỗi con đường chỉ có thể được ăn một lần, mặc dù không có gì ngăn cản bạn đi dọc theo những con đường nhiều lần. Ngoài ra Cayman không dừng lại trên đường. Tức là nếu anh ta bắt đầu di chuyển từ ngã tư này sang ngã tư khác, thì chắc chắn anh ta sẽ đi hết một vòng để đến ngã tư tiếp theo.
Khi bắt đầu giấc mơ, Caiman đang ở ngã tư số 0. Hãy giúp anh ta xác định số lượng bánh bao tối đa mà anh ta có thể ăn mà không bị con quái vật bánh bao độc ác tấn công.
Đầu vào:
Dòng đầu tiên chứa hai số nguyên n và k (3 ≤ n ≤ 10
5; 1 ≤ k ≤ 10
5) &mdash ; số lượng giao lộ và số lượt truy cập tối đa vào từng giao lộ.
N - 1 dòng tiếp theo chứa ba số nguyên u, v và C
u,v (0 ≤ u, v ≤ n - 1; 0 ≤ C
u,v ≤ 10000), nghĩa là các giao điểm có số u và v được nối với nhau bằng một con đường có C
u,v bánh bao.
Đảm bảo rằng các giao lộ và đường tạo thành một cái cây.
Đầu ra:
In ra một số nguyên - số bánh bao tối đa mà Caiman có thể ăn.
Ví dụ:
| Đầu vào |
Đầu ra |
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 |
Giải thích:
Trong ví dụ đầu tiên, bạn cần truy cập các giao lộ theo thứ tự sau: 0, 1, 5, 1, 3, 1, 0, 2, 6,&thinsp ;2, 7, ?2, ?8. Sau đó, anh ấy sẽ ăn tổng cộng 1+2+2+1+3+3+3 = 15 cái bánh bao.
Lưu ý rằng không có giao lộ nào được truy cập quá 3 lần.