केमन और पकौड़ी
Problem
केमैन का एक असामान्य सपना है, कि वह शहर के एक अजीब हिस्से में है। इस क्षेत्र को एक ट्री ग्राफ़ के रूप में दर्शाया जा सकता है, जहाँ कोने चौराहे हैं और किनारे दो-तरफ़ा सड़कें हैं जो इन चौराहों को जोड़ती हैं। कुल मिलाकर n चौराहे हैं और प्रत्येक की अपनी संख्या 0 से n-1 तक है।
लेकिन इस सपने में सब कुछ इतना बुरा नहीं है, क्योंकि यू और वी नंबर वाले चौराहों के बीच हर सड़क पर सी <उप>यू, वी पकौड़ी हैं! कैमान को पकौड़े बहुत पसंद हैं, इसलिए वह ज्यादा से ज्यादा खाना चाहता है, लेकिन एक समस्या है - अगर वह किसी भी चौराहे पर के से ज्यादा बार जाता है, तो उस पर एक दुष्ट गुलगुले राक्षस का हमला होगा।
हालाँकि यह एक सपना है, प्रत्येक सड़क पर पकौड़ी केवल एक बार खाई जा सकती है, हालाँकि कुछ भी आपको कई बार सड़कों पर चलने से नहीं रोकता है। साथ ही केमैन सड़कों पर नहीं रुकते। यानी, अगर वह एक चौराहे से दूसरे चौराहे पर जाना शुरू करता है, तो वह निश्चित रूप से अगले चौराहे तक जाएगा।
सपने की शुरुआत में, कैमान चौराहे नंबर 0 पर है। उसे यह निर्धारित करने में मदद करें कि वह डंपलिंग राक्षस द्वारा हमला किए बिना अधिकतम संख्या में डंपलिंग खा सकता है।
इनपुट:
पहली पंक्ति में दो पूर्णांक n और k हैं (3 ≤ n ≤ 105; 1 ≤ k ≤ 105) &mdash ; चौराहों की संख्या और प्रत्येक चौराहों पर विज़िट की अधिकतम संख्या।
अगली n - 1 पंक्तियों में तीन पूर्णांक हैं u, v और Cu,v (0 ≤ u, v ≤ n - 1; 0 ≤ Cu,v< /sub) > ≤ 10000), जिसका अर्थ है कि संख्या u और v वाले चौराहे Cu,v डंपलिंग वाली सड़क से जुड़े हुए हैं।
इस बात की गारंटी है कि चौराहे और सड़कें एक पेड़ बन जाती हैं।
आउटपुट:
एक पूर्णांक प्रिंट करें - केमन जितना डंपलिंग खा सकता है।
उदाहरण:
<तालिका सीमा = "1" सेलपैडिंग = "1" सेलस्पेसिंग = "1" शैली = "चौड़ाई: 500 पीएक्स;">
<शरीर>
| इनपुट |
आउटपुट |
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,&thinsp ;2, 7, ?2, ?8। फिर वह कुल 1+2+2+1+3+3+3 = 15 पकौड़े खाएगा।
ध्यान दें कि किसी भी चौराहे पर 3 बार से ज्यादा नहीं जाना चाहिए।