كيمان وزلابية
Problem
كيمان لديه حلم غير عادي ، أنه في مكان غريب من المدينة. يمكن تمثيل هذه المنطقة كرسم بياني شجرة ، حيث تكون الرؤوس عبارة عن تقاطعات والحواف عبارة عن طرق ثنائية الاتجاه تربط هذه التقاطعات. يوجد إجمالي عدد n التقاطعات ولكل منها رقمه الخاص من 0 إلى n-1.
لكن ليس كل شيء سيئًا للغاية في هذا الحلم ، لأنه في كل طريق بين التقاطعات بالأرقام u و v توجد زلابية C
u ، v ! يحب Caiman الزلابية كثيرًا ، لذا فهو يريد أن يأكل أكبر قدر ممكن من الطعام ، ولكن هناك مشكلة - إذا زار أي مفترق طرق أكثر من k مرة ، فسوف يهاجمه وحش زلابية شرير.
على الرغم من أن هذا حلم ، إلا أنه لا يمكن تناول الزلابية على كل طريق إلا مرة واحدة ، على الرغم من أن لا شيء يمنعك من المشي على طول الطرق عدة مرات. كما أن كايمان لا تتوقف على الطرق. بمعنى أنه إذا بدأ في الانتقال من تقاطع إلى آخر ، فإنه بالتأكيد سيقطع كل الطريق إلى التقاطع التالي.
في بداية الحلم ، كان Caiman على مفترق الطرق رقم 0. ساعده في تحديد الحد الأقصى لعدد الزلابية التي يمكنه تناولها دون أن يهاجمه وحش الزلابية الشرير.
الإدخال:
يحتوي السطر الأول على عددين صحيحين n و k (3 & le؛ n & le؛ 10 5 ؛ 1 & thinsp؛ & le؛ & thinsp؛ k & thinsp؛ & le؛ & thinsp؛ 10 5 ) & mdash؛ عدد التقاطعات والحد الأقصى لعدد الزيارات لكل من التقاطعات.
السطور التالية n - 1 تحتوي على ثلاثة أعداد صحيحة u و v و C u، v (0 & le؛ u، v & le؛ n - 1؛ 0 & le؛ C u، v & le؛ 10000) ، مما يعني أن التقاطعات مع الرقمين u و v متصلة بطريق مع زلابية C u، v .
مضمون أن تشكل التقاطعات والطرق شجرة.
الإخراج:
اطبع عددًا صحيحًا واحدًا - الحد الأقصى لعدد الزلابية التي يمكن أن يأكلها Caiman.
أمثلة:
نبسب ؛
<الجسم>
| إدخال |
الإخراج |
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، & thinsp؛ 1، & thinsp؛ 5، & thinsp؛ 1، & thinsp؛ 3، & thinsp؛ 1، & thinsp؛ 0، & thinsp؛ 2، & thinsp؛ 6، & thinsp ؛ 2، & thinsp؛ 7،؟ 2،؟ 8. ثم يأكل ما مجموعه 1 + 2 + 2 + 1 + 3 + 3 + 3 = 15 زلابية.
لاحظ أنه لم تتم زيارة أي تقاطع أكثر من 3 مرات.
نبسب ؛