Module: Pengaturcaraan Graf Dinamik


Problem

4 /7


Caiman dan ladu

Problem

Caiman mempunyai mimpi yang luar biasa, bahawa dia berada di bahagian bandar yang pelik. Kawasan ini boleh diwakili sebagai graf pokok, di mana bucunya adalah persimpangan dan tepi adalah jalan dua hala yang menghubungkan persimpangan ini. Terdapat n persimpangan secara keseluruhan dan setiap satu mempunyai nombor sendiri dari 0 hingga n-1.

Tetapi tidak semuanya begitu buruk dalam mimpi ini, kerana di setiap jalan antara persimpangan dengan nombor u dan v terdapat ladu Cu,v! Caiman sangat menyukai ladu, jadi dia ingin makan sebanyak mungkin, tetapi ada masalah - jika dia melawat mana-mana persimpangan lebih daripada k kali, dia akan diserang oleh raksasa dumpling yang jahat.

Walaupun ini adalah mimpi, ladu di setiap jalan hanya boleh dimakan sekali, walaupun tidak ada yang menghalang anda daripada berjalan di sepanjang jalan beberapa kali. Juga Cayman tidak berhenti di jalan raya. Iaitu, jika dia mula bergerak dari satu persimpangan ke persimpangan yang lain, maka dia pasti akan pergi ke persimpangan seterusnya.

Pada permulaan mimpi, Caiman berada di persimpangan nombor 0. Bantu dia menentukan bilangan maksimum ladu yang dia boleh makan tanpa diserang oleh raksasa ladu jahat.

Input:
Baris pertama mengandungi dua integer n dan k (3 ≤ n ≤ 105; 1 ≤ k ≤ 105) &mdash ; bilangan persimpangan dan bilangan maksimum lawatan ke setiap persimpangan.
N - 1 baris seterusnya mengandungi tiga integer u, v dan Cu,v (0 ≤ u, v ≤ n - 1; 0 ≤ Cu,v< /sub > ≤ 10000), bermakna persimpangan dengan nombor u dan v disambungkan oleh jalan dengan ladu Cu,v.
Dijamin bahawa persimpangan dan jalan raya membentuk pokok.

Output:
Cetak satu integer - bilangan maksimum ladu yang Caiman boleh makan.

Contoh:
 
Penjelasan:
Dalam contoh pertama, anda perlu melawati persimpangan dalam susunan berikut: 0, 1, 5, 1, 3, 1, 0, 2, 6,  ;2,  7, ?2, ?8. Kemudian dia akan makan sebanyak 1+2+2+1+3+3+3 = 15 ladu.
Ambil perhatian bahawa tiada persimpangan dilawati lebih daripada 3 kali.
 

time 2000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!

Input Output
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