در آسیا، یک امپراتوری باستانی به اسم مایو وجود داشت که یکی از قدرتمندترین امپراتوری‌های زمان خویش بود. در اول، امپراتوری فقط یک شهر داشت (که آن شهر پایتخت نیز بود)، اما چون مردم آن جنگجویان دلیری بودند، شروع به فتح کردن حکومت‌های همسایه کردند تا مرز خود را گسترش دهند.
هر وقت که آن‌ها حکومتی را شکست می‌دادند، همه شهرهارا جز بزرگترین شهر ویران می‌کردند، بزرگترین شهر را به قلمرو خود می‌افزودند و یک جاده از بزرگترین شهر به یکی از شهرهای خود می‌کشیدند که بتوانند بین همه شهرهای قلمرو خود سفر کنند. همچنین، اگر شهر تسخیرشده به اندازه کافی بزرگ بود، آن‌را پایتخت خود می‌کردند.
نفوذپذیری یکی از شهرهای مایو به صورت تعداد جاده‌های لازم برای رسیدن به پایتخت تعریف می‌شود.
ما لیست همه‌ی حکومت‌هایی که مایو شکست داده‌‌است و جاده‌هایی که ساخته‌است را داریم. می‌خواهیم بیش‌ترین میزان نفوذپذیری یک شهر را بعد از اضافه‌شدن هر شهر به مایو محاسبه کنیم. برای ساده‌شدن خروجی، $v_2 + v_3 + \cdots + v_n$ را چاپ کنید که $v_i$، بیش‌ترین نفوذپذیری یک‌شهر پس از اضافه شدن شهر $i$ام است.
به ازای هر تست، در یک خط، جمع بیش‌ترین نفوذپذیری را (همان‌طور که در صورت سوال ذکر شده‌است) چاپ کنید.
| ورودی نمونه | خروجی نمونه |
|---|---|
| 3 1 1 2 1 3 1 1 2 0 0 | 3 2 |
پاسخ
منتظر پر کردن این قسمت توسط علاقمندان هستیم.