درخت $T$ به ریشهی $r$ داده شده است. پدر رأس $v$ را در این درخت با $P(v)$ نمایش میدهیم و $P®$ را برابر خود $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$ بازی کند، حداکثر یک بار شمارده میشود.
در سطر $i$اُم، عدد مربوط به رأس $i$ را بنویسید.
| ورودی نمونه | خروجی نمونه |
|---|---|
| 5 3 1 1 2 2 3 3 4 4 5 | 5 3 3 3 7 |