वृक्ष का Centroid (सेंट्रॉइड) खोजें
आपको
v शीर्षों (vertices) वाला एक वृक्ष (tree) दिया गया है और आपका कार्य इस वृक्ष का सेंट्रॉइड (centroid) ढूँढना है। वृक्ष का सेंट्रॉइड वह शीर्ष होता है, जिसे हटाने पर शेष सभी उपवृक्षों का आकार (size) अधिकतम नोड्स (nodes) तक सीमित रहता है।इनपुट
इनपुट की पहली पंक्ति में एक अकेला पूर्णांक
v (1 ≤ v ≤ 100 000) दिया जाता है।अगली
v-1 पंक्तियों में प्रत्येक में दो पूर्णांक v1, v2 (1 ≤ v1, v2 ≤ v) आते हैं, जो示ाते हैं कि शीर्ष v1 शीर्ष v2 से जुड़ा हुआ है (और उल्टा भी)।आउटपुट
कार्यक्रम को दिए गए वृक्ष का सेंट्रॉइड प्रिंट करना चाहिए। यदि एक से अधिक संभावित उत्तर हों, तो कोई भी एक मान्य उत्तर छापा जा सकता है।
उदाहरण
इनपुट | आउटपुट |
3
1 2
1 3 | 1 |
5
1 2
2 3
3 4
3 5 | 3 |
Hint
आप प्रत्येक शीर्ष के लिए उसके उपवृक्ष का आकार (इसमें उसके सभी बच्चे शामिल हैं) निकाल सकते हैं।
उसके बाद, यह जाँचें कि प्रत्येक शीर्ष को हटाने पर उसके सभी उपवृक्षों का आकार पूरे वृक्ष के आधे, यानी , से अधिक तो नहीं हो रहा है (चाइल्ड उपवृक्षों के आकार के अलावा, मुख्य वृक्ष में बाकी बचे हिस्से का आकार
v - currentNodeSize से जाँचा जा सकता है)।Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB