Problem
کیمن خواب غیرمعمولی می بیند که در قسمتی عجیب از شهر است. این ناحیه را می توان به صورت نمودار درختی نشان داد که در آن رئوس تقاطع هستند و یال ها جاده های دو طرفه هستند که این تقاطع ها را به هم متصل می کنند. در مجموع n تقاطع وجود دارد و هر کدام از 0 تا n-1 عدد خاص خود را دارند.
اما در این رویا همه چیز آنقدر بد نیست، زیرا در هر جاده بین تقاطع هایی با اعداد u و v کوفته های C
u,v وجود دارد! کیمن خیلی کوفته دوست دارد، بنابراین می‌خواهد تا آنجا که ممکن است بخورد، اما یک مشکل وجود دارد - اگر او از هر چهارراهی بیش از k بار بازدید کند، مورد حمله یک هیولای شیطان صفت قرار می‌گیرد.
اگرچه این یک رویا است، اما کوفته های موجود در هر جاده را فقط می توان یک بار خورد، اگرچه هیچ چیز مانع از آن نمی شود که چندین بار در جاده ها قدم بزنید. همچنین کیمن در جاده ها متوقف نمی شود. یعنی اگر شروع به حرکت از یک تقاطع به تقاطع دیگر کند، قطعاً تا چهارراه بعدی خواهد رفت.
در ابتدای رویا، کیمن در چهارراه شماره 0 قرار دارد. به او کمک کنید تا حداکثر تعداد کوفته هایی را که می تواند بخورد بدون اینکه مورد حمله هیولای شیطان صفت قرار گیرد، تعیین کند.
ورودی:
خط اول شامل دو عدد صحیح n و k (3 ≤ n ≤ 10
5; 1 ≤ k ≤ 10
5) &mdash ; تعداد تقاطع ها و حداکثر تعداد بازدید از هر یک از تقاطع ها.
خطوط بعدی n - 1 شامل سه عدد صحیح u، v و C
u,v هستند (0 ≤ u, v ≤ n - 1; 0 ≤ C
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
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 |
توضیح:
در مثال اول، باید از تقاطع ها به ترتیب زیر بازدید کنید: 0, 1, 5, 1, 3, 1, 0, 2, 6, ;2, 7, ?2, ?8. سپس در مجموع 1+2+2+1+3+3+3 = 15 کوفته می خورد.
توجه داشته باشید که هیچ تقاطعی بیش از 3 بار بازدید نمی شود.