حلم غريب لقسطنطين
Problem
بمجرد أن شارك قسطنطين في الأولمبياد التالي ، وهو الأولمبياد الدولي الثالث عشر بالفعل ، كان يعود إلى الوطن بالقطار. كما هو الحال دائمًا ، جلس وفكر في معنى الحياة ، وحل مشكلات البرمجة في وقت واحد. بعد مرور بعض الوقت ، غاب كونستانتين ، لكن المشكلة أنه لكي يستيقظ ، يجب أن يحل المشكلة التي ظهرت في رأسه ، والتي تطارده!
هذه المرة ، حلم كونستانتين بشجرة تتكون في البداية من رأس واحد فقط برقم 1. في المشكلة التي حددها ، تمت إضافة رؤوس جديدة تدريجياً إلى الشجرة. في الثانية i ، تمت إضافة رأس برقم i + 1 إلى الشجرة ، والذي تم تعليقه كإبن من الرأس p
i ، وعلى الحافة بين الرؤوس i + 1 و p
i الحرف c
أنا مكتوب.
يتوافق كل مسار من جذر الشجرة إلى الرأس v مع سلسلة معينة تم الحصول عليها عن طريق كتابة الرموز المكتوبة على حواف المسار الحالي بالترتيب من الجذر إلى الرأس v. واجه كونستانتين مهمة صعبة للوهلة الأولى - بعد كل إضافة لقمة جديدة ، احسب عدد السلاسل الفريدة التي تبدأ من جذر الشجرة (الرأس رقم 1) وتنتهي عند قمة أخرى. & nbsp ؛
في حلمه ، قسطنطين ليس عبقريًا على الإطلاق ، لذلك هو نفسه لا يستطيع حل هذه المشكلة. ساعد كونستانتين في حل المشكلة واستيقظ.
الإدخال:
يحتوي السطر الأول على الرقم n - عدد الطلبات لإضافة عقدة جديدة إلى الشجرة (1 & lt ؛ = n & lt ؛ = 300000).
تصف الأسطر n التالية طلبات إضافة الرؤوس. يتم وصف الاستعلام الأول بواسطة المعلمات p i (1 & lt؛ = p i & lt؛ = i) و c i ، والتي يعني أن الرأس المضاف بالرقم i + 1 معلق من الرأس بالرقم p i كطفل ، والرمز c i مكتوب على الحافة الناتجة - حرف صغير من الأبجدية اللاتينية.
الإخراج:
طباعة س سطور. في السطر الأول ، اطبع الإجابة على مشكلة كونستانتين بعد إضافة رأس i + 1-th.
أمثلة:
نبسب ؛
<الجسم>
| إدخال |
الإخراج |
2
1 ب
2p |
1
2 |
3
1 س
1 س
2 ي |
1
1
2 |