- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۵۱۲ مگابایت
در یک شرکت برنامه‌نویسی، $n$ برنامه‌نویس مشغول به کار هستند. این برنامه‌نویس‌ها با اعداد ۱ تا $n$ شماره‌گذاری می‌شوند. سیستم مدیریتی این شرکت به صورت یک درخت است. یعنی هر برنامه‌نویس به جز برنامه‌نویس شماره‌ی ۱، یک مدیر دارد. مدیر برنامه‌نویس $i$ را با $p_i$ نشان می‌دهیم. در واقع ساختار این شرکت به صورت یک درخت ریشه‌دار است.
عید نوروز نزدیک است و این برنامه‌نویس‌ها می‌خواهند از شرکت خارج شوند و برای سفر به شهر کدکاپ بروند. زمانی برنامه‌نویس شماره‌ی $i$ می‌تواند از شرکت خارج شود که $p_i$ هم از سازمان خارج شده باشد.
برای هر $k$ از ۱ تا $n$ حساب کنید چند زیرمجموعه $k$ عضوی از برنامه‌نویس‌ها می‌توانند از شرکت خارج شوند. چون ممکن است پاسخ خیلی بزرگ باشد، باقی‌مانده‌ی آن را بر $10^9 + 7$ چاپ کنید.
ورودی
در سطر اول ورودی، عدد صحیح و مثبت $n$ آمده که تعداد برنامه‌نویس‌های شرکت را نشان می‌دهد. $$2 \leq n \leq 10 , 000$$
در سطر دوم ورودی، $n - 1$ عدد صحیح $p_2, p_3, \dots, p_n,$ می‌آید. $$1 \leq p_i \lt i$$
خروجی
خروجی $n$ سطر دارد و در سطر $k$ام تعداد حالت‌هایی که $k$ نفر شرکت را ترک کنند محاسبه کنید.
مثال‌ها
ورودی نمونه ۱
3
1 1
خروجی نمونه ۱
1 2 1
توضیح نمونه ۱
- برای حالت $k = 1$ فقط باید یک برنامه‌نویس شرکت را ترک کند و آن فقط $1$ است. (۱ حالت)
- برای حالت $k = 2$ فقط باید دو برنامه‌نویس شرکت را ترک کنند و آن‌ها می‌توانند $1, 2$ یا $1, 3$ باشند. (۲ حالت)
- برای حالت $k = 3$ فقط باید سه برنامه‌نویس شرکت را ترک کنند و آن‌ها می‌توانند $1, 2, 3$ هستند. (۱ حالت)
ورودی نمونه ۲
5
1 1 2 2
خروجی نمونه ۲
1 2 3 3 1
توضیح نمونه ۲
مشابه نمونه‌ی قبل مجموعه افرادی که می‌توانند خارج شوند عبارت است از:
$$k = 1 \to {1}$$ $$k = 2 \to {1, 2}, {1, 3}$$ $$k = 3 \to {1, 2, 3}, {1, 2, 4}, {1, 2, 5}$$ $$k = 4 \to {1, 2, 3, 4}, {1, 2, 3, 5}, {1, 2, 4, 5}$$ $$k = 5 \to {1, 2, 3, 4, 5}$$
ارسال پاسخ برای این سؤال