المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:متفرقه:سوال های ای سی ام سایت تهران:دوره ی ۱۲:k

The Mayo Empire

در آسیا، یک امپراتوری باستانی به اسم مایو وجود داشت که یکی از قدرتمندترین امپراتوری‌های زمان خویش بود. در اول، امپراتوری فقط یک شهر داشت (که آن شهر پایتخت نیز بود)، اما چون مردم آن جنگجویان دلیری بودند، شروع به فتح کردن حکومت‌های همسایه کردند تا مرز خود را گسترش دهند.

هر وقت که آن‌ها حکومتی را شکست می‌دادند، همه شهرهارا جز بزرگ‌ترین شهر ویران می‌کردند، بزرگترین شهر را به قلمرو خود می‌افزودند و یک جاده از بزرگ‌ترین شهر به یکی از شهرهای خود می‌کشیدند که بتوانند بین همه شهرهای قلمرو خود سفر کنند. همچنین، اگر شهر تسخیرشده به اندازه کافی بزرگ بود، آن‌را پایتخت خود می‌کردند.

نفوذپذیری یکی از شهرهای مایو به صورت تعداد جاده‌های لازم برای رسیدن به پایتخت تعریف می‌شود.

ما لیست همه‌ی حکومت‌هایی که مایو شکست داده‌‌است و جاده‌هایی که ساخته‌است را داریم. می‌خواهیم بیش‌ترین میزان نفو‌ذپذیری یک‌ شهر را بعد از اضافه‌شدن هر شهر به مایو محاسبه کنیم. برای ساده‌شدن خروجی، $v_2 + v_3 + \cdots + v_n$ را چاپ کنید که $v_i$،‌ بیش‌ترین نفوذپذیری یک‌شهر پس از اضافه شدن شهر $i$ام است.

ورودی

  • تست‌های مختلفی در ورودی وجود دارد. در خط اول هر تست عدد$n$($1 \leq n \leq 100000$)، تعداد شهرهای مایو داده می‌شود. شهرها به‌ترتیب اضافه‌شدن به امپراتوری از ۱ تا $n$ شماره‌گذاری شده‌اند. یعنی اول کار تنها شهر ۱ وجود دارد و پایتخت است.
  • سپس در هر یک از $n-1$ خط بعد دو عدد $j$ و $c$ آمده‌اند که یعنی شهر $i+1$ از طریق جاده به شهر $j$ وصل شده‌است و $c$ اگر ناصفر باشد یعنی این شهر از این پس پایتخت خواهد شد و درغیر این‌صورت صفر خواهد بود.
  • در آخرین خط ورودی عدد ۰ آمده‌است.

خروجی

به ازای هر تست، در یک خط، جمع بیش‌ترین نفوذپذیری را (همان‌طور که در صورت سوال ذکر شده‌است) چاپ کنید.

محدودیت‌ها

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

ورودی و خروجی نمونه

ورودی نمونه خروجی نمونه
3
1 1
2 1
3
1 1
2 0
0
3
2

پاسخ

منتظر پر کردن این قسمت توسط علاقمندان هستیم.


ابزار صفحه