बंकरों
पेड़ों को कुशलतापूर्वक हैश करने के भी कई तरीके हैं।
इन विधियों में से एक को निम्नानुसार व्यवस्थित किया गया है:
गहराई में ट्रैवर्सल के क्रम में, हम शीर्षों को पुनरावर्ती रूप से संसाधित करते हैं। हम मानेंगे कि एकल शीर्ष का हैश p के बराबर है। बच्चों के साथ कोने के लिए, हम पहले उनके लिए एल्गोरिथम चलाते हैं, फिर बच्चों के माध्यम से हम वर्तमान सबट्री के हैश की गणना करेंगे। ऐसा करने के लिए, बच्चों के सबट्री के हैश को संख्याओं के अनुक्रम के रूप में मानें और इस क्रम से हैश की गणना करें। यह मौजूदा सबट्री का हैश होगा।
अगर चिल्ड्रन पर ऑर्डर हमारे लिए महत्वपूर्ण नहीं है, तो हैश की गणना करने से पहले, हम चाइल्ड सबट्री से हैश के क्रम को सॉर्ट करते हैं और फिर सॉर्ट किए गए क्रम से हैश की गणना करते हैं।
इस तरह आप पेड़ों के समरूपता की जांच कर सकते हैं - बस बच्चों पर बिना आदेश के हैश की गिनती करें (यानी, हर बार बच्चों के हैश को छांटते हुए)। और अगर जड़ों का हैश मेल खाता है, तो पेड़ आइसोमॉर्फिक हैं, अन्यथा नहीं।
बिना जड़ वाले वृक्षों के लिए सब कुछ एक समान तरीके से होता है, लेकिन केन्द्रक को जड़ के रूप में लिया जाना चाहिए। या दो सेंट्रोइड्स होने पर हैश की एक जोड़ी पर विचार करें।
Problem
पेट्या और वास्या उत्साह से जासूस खेलते हैं। आज वे योजना बना रहे हैं कि वे
कहां होंगे
उनके गुप्त बंकर और मुख्यालय स्थित हैं।
अब तक, पेट्या और वस्या ने फैसला किया है कि उन्हें ठीक n बंकरों की आवश्यकता होगी, जिन्हें गोपनीयता के लिए 1 से n तक गिना जाएगा।
उनमें से कुछ दो-तरफ़ा सुरंगों से जुड़े होंगे, और विश्वसनीयता और गोपनीयता के लिए, सुरंगों तक किसी भी बंकर से किसी एक रास्ते से पहुंचा जा सकेगा।
पेट्या और वस्या ने यह भी तय किया कि कौन से बंकरों को सुरंगों से जोड़ा जाएगा, लेकिन वे यह नहीं चुन सकते कि कौन सा बंकर मुख्यालय होगा।
लड़के इसे चुनना चाहते हैं और शेष बंकरों को आपस में बांटना चाहते हैं ताकि उन्हें समान संख्या में बंकर मिलें। बिल्कुल दो सुरंगें मुख्यालय की ओर जाती हैं: एक वास्या के बंकर से, दूसरी पेट्या के बंकर से।
थके हुए पेट्या अपने घर चले गए, और सुबह वास्या ने उन्हें एक योजना दिखाई जिसमें बंकरों को डॉट्स और सुरंगों को खंडों के साथ चिह्नित किया गया था।
इसके अलावा, वास्या ने मुख्यालय को इस तरह से चुना कि उन्होंने जो योजना बनाई वह उस बिंदु से गुजरने वाली सीधी रेखा के संबंध में सममित थी जो मुख्यालय से मेल खाती थी।
हालाँकि पेट्या ने लगभग तुरंत वास्या को दिखाया कि उसने एक गलती की है और बंकरों का आधा हिस्सा नहीं बनाया है, उसने सोचा कि क्या मुख्यालय चुनना और ऐसी सममित योजना बनाना संभव है।
इनपुट:
इनपुट फ़ाइल की पहली पंक्ति में एक पूर्णांक n (1 <= n <= 105) - डिब्बे की संख्या होती है।
अगली n - 1 पंक्तियों में दो पूर्णांक हैं ui और vi (1 <= ui, vi <= n, ui ≠ vi) - i-th सुरंग से जुड़े बंकरों की संख्या।
इस बात की गारंटी है कि किन्हीं भी दो बंकरों के बीच केवल एक ही रास्ता है।
आउटपुट:
आउटपुट फ़ाइल में "हाँ" प्रिंट करें यदि मुख्यालय चुनना और ऐसी योजना बनाना संभव है, या "नहीं" यदि यह संभव नहीं है।
उदाहरण:
<तालिका सीमा = "1" सेलपैडिंग = "1" सेलस्पेसिंग = "1" शैली = "चौड़ाई: 500 पीएक्स;">
<शरीर>
| इनपुट |
आउटपुट |
2
1 2
| नहीं |
3
1 2
2 3
| हाँ |