ویلی ونکا
ویلی ونکا که صاحب کارخانهی شکلاتسازی ونکا است، با دیدن تار مویی سفید بر روی سرش، تصمیم به انتخاب جانشین مناسبی برای کارخانهی خود میگیرد. اما با وجود آقا داوود، دیگر نیازی به پخش کردن بلیطهای طلایی نمیبیند. او آقا داوود را به کارخانهاش دعوت میکند تا توانایی او در ادارهی کارخانه را بسنجد. برای این کار او مسئلهای به این صورت برای آقا داوود مطرح میکند: «درختی ریشهدار $N$ راسی داریم که از راس 1 ریشهدار شده است و راس 1 دقیقا شامل یک فرزند است. این درخت در واقع بیانگر سیستم شکلاتسازی در کارخانهی ونکا است، به طوری کهیالهای درخت مسیر رودخانههای شکلاتی را نشان میدهند که در کارخانه تولید میشود. حال در هر یک از برگهای این درخت (منظور از برگ، راسهای با درجهی یک در درخت به جز راس ریشه است) یک نوع شکلات با طعمی مخصوص و متفاوت از سایر برگها نگهداری میشود که با باز کردن منبع هر برگ شکلاتهای داخل آن بر روی تمامی یالهای مسیر آن راس تا ریشه، جاری میشود. حال آقا داوود باید $K$ تا از این برگها را انتخاب کند، به طوری که تعداد مزههایی متفاوتی که در اثر باز کردن منبع این $K$ برگ به وجود میآید، بیشینه شود. مزهی داخل یک یال به وسیلهی تمامی مزههایی که از آن یال عبور میکند تعیین میشود. در واقع مزهی شکلات جاری در دو یال با یکدیگر متفاوت است، اگر و فقط اگر برگی وجود داشته باشد که منبع آن باز شده و مواد آن تنها از یکی از این یالها عبور کند.» حال شما باید بیشترین تعداد مزههای متفاوتی که آقا داوود میتواند بسازد را در خروجی چاپ کنید. برای توضیح بیشتر دربارهی مسئله به توضیحات ورودیهای نمونه توجه کنید.
ورودی
- سطر اول ورودی شامل دو عدد طبیعی، $ 1\leq N \leq 500$، تعداد راسهای درخت و $1 \leq K < N$، تعداد برگهایی که باید انتخاب شود، است.
- سطر دوم شامل $1 \leq P_2,P_3,…,P_N \leq N$، است که $P_i$ پدر راس شمارهی $i$ را نشان میدهد.
- تضمین میشود که درخت داده شده شامل حداقل $K$ برگ است و همچنین راس شمارهی 1، دقیقا شامل یک فرزند است.
- در ۳۰ درصد از ورودیها، تعداد برگهای درخت حداکثر ۲۵ تاست.
خروجی
در تنها سطر خروجی، بیشترین تعداد مزهی قابل تولید را چاپ کنید.
محدودیتها
- محدودیت زمان: ۲ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
ورودی و خروجی نمونه
| ورودی نمونه | خروجی نمونه |
|---|---|
| 5 2 1 2 2 2 | 3 |
| 8 4 1 2 2 3 3 4 4 | 7 |
توضیحات ورودی
- در ورودی اول، راسهای 4،3 و 5 برگ هستند. حال اگر برگهای 3 و 4 به عنوان برگهای انتخابی آقا داوود باشند، یال (2،3) شامل مزهی شمارهی 3، یال (2،4) شامل مزهی شمارهی 4، و یال (1،2) شامل مخلوطی از مزههای 3 و 4 است.
- در ورودی دوم، راسهای 7،6،5 و 8 برگ هستند. حال آقا داوود همهی برگها را انتخاب میکند و در این صورت در تمامی یالها مزهی متفاتی ایجاد میشود.