+ محدودیت زمان: ۱٫۵ ثانیه + محدودیت حافظه: **۵۱۲ مگابایت** ---------- «مِسِریکس» از گرمایش جهانی به ستوه آمده و قصد دارد از خلاّقیّتش در زمینه‌ی بحران محیط زیست استفاده کند؛ امّا... مسریکس می‌خواهد گریزی بزند به روابط فامیلی بلکه بتواند راه حل رفع بحران محیط زیست را از این طریق بیابد. از نظر مسریکس، گام نخست تحقیق در این زمینه، تسلّط بر تعاریف زیر است. + پدر: این تعریف خیلی جدیدی نیست. هر کسی(به جز بزرگ‌خاندان) فرزند دقیقا یک انسان دیگر است که آن را پدرش می‌نامیم. + بزرگ‌خاندان: کسی که فرض می‌کنیم پدری ندارد. + پدرِ $i$-ام: اگر $i > 0$ باشد، پدرِ پدرِ $i-1$-ام یک انسان را پدر $i$-ام او می‌نامیم. پدر ۰-ام هر کسی، خود او است. + عمو: می‌گوییم انسان $X$ عموی انسان $Y$ است اگر و فقط اگر پدر $a$-ام $X$ و پدر $b$-ام $Y$ برابر باشند. + دایی: می‌گوییم انسان $X$ دایی انسان $Y$ است اگر و فقط اگر پدر $c$-ام $X$ و پدر $d$-ام $Y$ برابر باشند. دقّت کنید که در تعریف عمو، پدر $a$-ام $X$ یا پدر $b$-ام $Y$ وجود نداشته باشند، $X$ عموی $Y$ نخواهد بود. هم‌چنین اگر در تعریف دایی، پدر $c$-ام $X$ و یا پدر $d$-ام $Y$ وجود نداشته باشد نیز $X$ دایی $Y$ نخواهد بود. روزی مسریکس داشت با میسیکس، که علاوه بر دوست قدیمی مسریکس، یکی از اقوام دور او هم هست، در خیابان قدم می‌زد و در مورد بحران محیط زیست صحبت می‌کرد که ناگهان دو نفر جلوی آن‌ها را گرفتند و از مسریکس پرسیدند: «میسیکس چه نسبتی با تو داره؟» و «تو چه نسبتی با میسیکس داری؟». مسریکس برای پاسخ دادن به این سوال چند لحظه در فکر فرو رفت. و به نکته‌ی جالبی پِی برد؛ هر دو آن‌ها می توانستند با دنباله‌ای از کلمات عمو و دایی نسبتشان با یکدیگر را توضیح دهند؛ مثلن در جواب سوال اوّل مسریکس می‌توانست بگوید: «میسیکس **عمویِ عمویِ داییِ داییِ** من است.» و در جواب سوال دوم بگوید: «من **داییِ عمویِ عمویِ داییِ** میسیکس هستم.» ناگهان مسریکس به نکته‌ی جالب‌تری پی برد؛ بله او پارامتر جدیدی پیدا کرد که واقعا در بحران محیط زیست مؤثر است؛ این پارامتر را در خانواده‌ی مسریکس محاسبه کنید و به او بگویید. فرض کنید که خانواده از $n$ نفر تشکیل شده باشد و هر انسان را با عددی یکتا از $1$ تا $n$ نمایش دهیم. بزرگ‌خاندان همواره با عدد ۱ مشخّص می‌شود. و پدر هر کسی به جز بزرگ‌خاندان شخصی یکتاست. شما باید تعداد جفت انسان‌هایی را بشمرید که ‌می‌توانند همدیگر را با دنباله‌ای از کلمات **عمو** و **دایی** صدا بزنند. # ورودی در سطر اوّل ورودی عدد $n$ می‌آید. در سطر دوم دو عدد $a$ و $b$ می‌آیند. در سطر سوم نیز دو عدد $c$ و $d$ می‌آیند. هر یک از $n - 1$ خط بعد نشان‌دهنده‌ی پدر انسان‌ها هستند. در خط $i$-ام شماره‌ی پدر انسان $i + 1$-ام می‌آید. تضمین می‌شود که شماره‌ی پدر هر کسی از شماره‌ی خود او کوچک‌تر است. $$1 \leq a, b, c, d \leq n \leq 500\ 000$$ # خروجی در تنها سطر خروجی باید تعداد جفت‌هایی که می‌توانند هم‌دیگر را با دنباله‌ای از کلمات **عمو** و **دایی** صدا کنند، چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 5 1 3 2 1 1 2 2 4 ``` ## خروجی نمونه ۱ ``` 6 ``` در این مثال همه جفت‌ها به جز جفت‌هایی که شامل راس ۱ هستند، می توانند یکدیگر را با دنباله‌ای از کلمات عمو و دایی صدا بزنند.

حل سؤال در بانک سؤالات