• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

---

امروز روز جهانیه ریاضیاته! و «ترکیبیات» یکی از پیچیده‌ترین مباحث اونه...

%align_center_start%

دکتر فریدون درخشانی

%align_end%

در کوئرا $n$ نفر مشغول به کارند. این $n$ نفر را با اعداد $1, 2, 3, \dots ,n$ نشان می‌دهیم. سیستم کاری شرکت به صورت یک درخت ریشه‌دار است. یعنی هر کس به جز مدیرعامل (که با عدد $1$ نشان داده می‌شود.)‌ یک مدیر دارد. مدیر کارمند با شماره $i$ را با $par_i$ نشان می‌دهیم. همواره $par_i < i$ است.

یک روز یک شعبده باز وارد کوئرا می‌شود و می‌خواهد اعضای شرکت را به چالش بکشد.

روند شعبده بازی به صورت زیر است:

شعبده باز می‌خواهد روی سر هر کدام از اعضای شرکت یک کلاه قرار دهد. هر کلاه می‌تواند به یکی از $c$ رنگ $1, 2, 3, \dots, c$ رنگ‌آمیزی شده باشد. هیچ کس رنگ کلاه روی سرش را نمی‌بیند و فقط می‌توند رنگ کلاه مدیر خود و اعضایی از شرکت را ببیند که مدیر مستقیم آنان است. (همه اعضای شرکت مقدار $c$ و ساختار درختی شرکت را می‌دانند.)

بعد از پایان کلاه گذاری هر کس یک حدس خصوصی درباره رنگ کلاه خودش می‌زند. (یعنی این حدس را بلند اعلام نمی‌کند و هیچ کس حدس هیچ کسی را نمی‌بیند.) توجه کنید بعد از شروع کلاه گذاری توسط شعبده باز هیچ ارتباطی بین اعضای شرکت مجاز نیست و فقط رنگ کلاه مدیر و زیردستان قابل روئیت است.

هدف اعضای شرکت کوئرا بیشینه کردن مجموع حدس‌های درست است.

بعد از اینکه شعبده باز قاعده بازی را توضیح داد به اعضای شرکت اجازه داد که کمی باهم مشورت کنند و به یک استراتژی دست جمعی برسند. (توجه کنید خود شعبده باز هم در شرکت حضور دارد و استراتژی را می‌داند.)

بعد از پایان مشورت کلاه گذاری توسط شعبده باز آغاز می‌شود. اگر فرض کنیم که اعضای کوئرا بهترین استراتژی را برای بیشینه کردن حدس‌ها انتخاب می‌کند و شعبده باز هم کلاه گذاری را انتخاب می‌کند که کمترین حدس درست را اعضای شرکت بزنند. تعداد حدس‌های درست در نهایت بیابید.

توجه کنید استراتژی اعضای شرکت نمی‌تواند به شانس بستگی داشته باشد و کاملا به صورت تصمیم پذیر حدس‌ها را مشخص می‌کند. (یعنی قبل از هر روش کلا‌ه گذاری، شعبده باز می‌تواند همه حدس‌ها را بفهمد چون استراتژی اعضای شرکت را می‌داند.)

ورودی

در سطر اول ورودی دو عدد صحیح و مثبت $n$ و $c$ که با یک فاصله از هم جدا شده‌اند آمده است و به ترتیب نشان دهنده‌ی تعداد اعضای شرکت و تعداد رنگ‌های مختلف کلاه‌ها است.

$$2 \leq n \leq 100 , 000$$ $$1 \leq c \leq 10 $$

در سطر دوم ورودی $n - 1$ عدد صحیح و مثبت با فاصله از هم آمده است که عدد $i$ام شماره مدیر عضو $i + 1$ام یا همان $par_{i+1}$ را نشان می‌دهد. $$par_{i +1} \leq i $$

خروجی

در تنها سطر خروجی بیشینه حدس درست که اعضای کوئرا می‌توانند تضمین کنند خواهند داشت را چاپ کنید.

مثال

ورودی نمونه ۱

2 3
1

خروجی نمونه ۱

0

هر استراتژی که اعضای شرکت داشته باشند، شعبده‌باز می‌تواند طوری کلا‌ه‌ها را روی سر اعضای شرکت بگذارد که هیچ کدام از اعضا نتوانند حدس درستی بزنند.

ورودی نمونه ۲

2 2
1

خروجی نمونه ۲

1

در این ساختار شرکت، ۱ رنگ کلاه ۲ و ۲ رنگ کلاه ۱ را می‌بیند. استراتژی اعضای شرکت به این صورت است که ۱ رنگ کلاه ۲ و ۲ رنگ مخالف کلاه ۱ را حدس می‌زند. بنابراین اگر رنگ کلاه این دو نفر یکسان باشد حدس ۱ و اگر رنگ کلاه این دو نفر متفاوت باشد حدس ۲ درست خواهد بود. پس این استراتژی همواره یک حدس درست به ازای هر روش کلاه‌گذاری ایجاد می‌کند. همچنین هیچ استراتژی وجود ندارد که بتوان با کمک آن ۲ حدس درست ایجاد کرد.

ورودی نمونه ۳

5 1
1 2 2 4

خروجی نمونه ۳

5

در این حالت هر کس می‌تواند رنگ کلاه خودش را به درستی حدس بزند.