درخت ‎$T$‎ به ریشه‌ی ‎$r$‎ داده شده است. پدر رأس ‎$v$‎ را در این درخت با ‎$P(v)$‎ نمایش می‌دهیم و ‎$P(r)$‎ را برابر خود ‎$r$‎ در نظر می‌گیریم. حال پدر ‎$i$‎اُمِ رأس ‎$v$ (با نشان ‎$P^i(v)$‎) به این صورت تعریف می‌شود که ‎$P^0(v)=v$‎ و برای ‎$i>0$‎ داریم ‎$P^i(v)=P(P^{i-1}(v))$‎.

اکنون از شما خواسته‌شده تا برای هر رأسِ ‎$v$‎ جمع اندیس‌های پدر ‎$k$‎اُمِ ‎$v$‎ و پدران بالاترش (تا ریشه) را حساب کنید. دقّت کنید که اگر رأس ‎$u$‎، هم‌زمان نقش چندین پدر را برای رأس ‎$v$‎ بازی کند، حداکثر یک‌ بار شمارده می‌شود.

• در سطر اوّل ورودی ‎$n$‎، ‎$r$‎ و ‎$k$‎ آمده‌اند.
• در ‎$n-1$‎ سطر بعد در هر سطر دو سر یک یال درخت آمده است.
• می‌توانید فرض کنید که رئوس درخت در بازه‌ی ‎$[1..n]$‎ قرار دارند.
• ‎ $1\leq k,n\leq 500000$‎

در سطر ‎$i$اُم، عدد مربوط به رأس ‎$i$‎ را بنویسید.

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

• سوال بعد
• سوال قبل