+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت + روز ۲ دوره ۳۱ ---------- داوود و مشتلی برای تعطیلات به سواحل هاوایی رفتند و در طی عملیاتی مشتلی به داوود چندین هکتار از زمین‌های هاوایی را بدهکار شد. نقشه سواحل هاوایی به شکل یک درخت هست ولی هنوز دانشمندان اطلاعات دقیقی از شکلش به دست نیاورده‌اند. حالا مشتلی میخواهد از دست داوود فرار کند. از اونجا که این پول‌ها برای داوود عددی حساب نمی‌شود، فقط در صورتی از مشتلی پول‌ها را طلب می‌کند که فاصله‌اش از مشتلی کمتر از $d$ باشد. مشتلی که طلای المپیاد حسابداری دارد، به حساب و کتاب روی می‌آورد. مشتلی ارزش یک درخت را برابر تعداد راس‌هایی از درخت مثل $v$ تعریف می‌کند که اگر داوود در راس $v$ باشد ، مشتلی بتواند در راسی قرار بگیرد که فاصله‌اش از داوود بیشتر یا مساوی از $d$ باشد. شایان از زمین‌شناسان معروف قرن $21$ است و در مورد سواحل هاوایی تحقیق می‌کند. او درختی $n$ راسی و ریشه‌دار که طبق معمول ریشه‌اش راس $1$ است را به مشتلی می‌دهد و میگوید نقشه سواحل هاوایی یکی از زیردرخت‌های این درخت است. حال مشتلی، درخت شایان و عدد $d$ را به شما ورودی می‌دهد و در قبال آن می‌خواهد به ازای هر راس مثل $v$، ارزش زیردرخت $v$ را به دست آورید. در یک درخت ریشه‌دار، زیردرخت راس $v$ شامل تمام رئوس مانند $u$ است که در کوتاه‌ترین مسیر بین ریشه و $u$ راس $v$ ظاهر شده باشد. # ورودی در خط اول دو عدد $n$ و $d$ آمده است. در خط بعدی $n-1$ عدد است که در جایگاه $i$ ام پدر راس $i+1$ ام آمده است. $$ 2 \leq n \leq 3\times10^5$$ $$ 1 \leq d \leq n$$ # خروجی در یک خط $n$ عدد چاپ کنید که عدد $i$ ام ارزش زیردرخت راس $i$ است. # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت |:------------------:|:----------:|:------------------:| | ۱ | ۷ | $n \le 300$ | | ۲ | ۱۲ | $n \le 3000$ | | ۳ | ۱۷ | ارتفاع درخت حداکثر ۴۰ است | | ۴ | ۴۳ | $n \le 10^5$ | | ۵ | ۲۱ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 3 2 1 2 ``` ## خروجی نمونه ۱ ``` 2 0 0 ``` ## ورودی نمونه ۲ ``` 11 4 1 1 2 2 3 4 5 8 8 10 ``` ## خروجی نمونه ۲ ``` 11 7 0 0 0 0 0 0 0 0 0 ``` ## ورودی نمونه ۳ ``` 11 3 1 1 2 2 3 4 5 8 8 10 ``` ## خروجی نمونه ۳ ``` 11 8 0 0 3 0 0 2 0 0 0 ```

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