المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:متفرقه:آزمون های اینترنتی ۸۹ تا ۹۱:سوال ۴۶

Mayo

در تاریخ آسیا کشوری به نام ‎Mayo‎ وجود داشته که یکی از قوی‌ترین کشورهای زمان خود بوده است.

‎ این کشور در ابتدا شامل تنها یک شهر بوده و آن شهر پایتخت ‎Mayo‎ بوده است. مردم ‎Mayo‎ به مرور زمان با کشورهای همسایه وارد جنگ شدند و هر بار یک کشور را غارت کرده و آن را به عنوان یک شهر جدید به کشور خود اضافه می‌کردند. هم‌چنین برای این که بتوانند بین تمام شهرهای خود حرکت کنند، یک جاده بین شهر جدید و یکی از شهر های قدیمی احداث می‌کردند و در صورتی که شهر جدید به اندازه کافی بزرگ می‌بود، آن شهر را به عنوان پایتخت جدید ‎Mayo‎ انتخاب می‌کردند. ‎

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

ورودی

  • در سطر اول ورودی عدد ‎$1 \leq n \leq 10^5$‎ آمده که تعداد شهرهای نهایی ‎Mayo‎ را نشان می‌دهد.
  • در ‎$n-1$‎ سطر بعدی، در هر سطر دو عدد ‎$a_i$‎ و ‎$b_i$‎ آمده که نشان می‌دهد شهر ‎$i$‎ام پس از اضافه شدن به Mayo‎ به شهر ‎$a_i$‎ با جاده متصل شده و در صورتی که ‎$b_i$‎ برابر با ‎$1$‎ باشد پایتخت جدید ‎Mayo‎ به این شهر انتقال یافته است.‎
  • شهرهای ‎$2$‎ تا ‎$n$‎ به ترتیب به ‎Mayo‎ اضافه شده‌اند.‎

خروجی

در ‎$n-1$‎ سطر خروجی در هر سطر پاسخ سوال را چاپ نمایید.

محدودیت‌ها

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

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

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

پاسخ

قضیه: به ازای هر درخت ‎$T$‎ و راس ‎$u$‎، اگر ‎$v$‎ راسی باشد که فاصله آن از ‎$u$‎ بیشینه باشد، یکی از بلندترین مسیرهای گراف از ‎$v$‎ شروع می‌شود. ‎

با استفاده از این قضیه ‎ می‌توان نشان داد اگر درخت ‎$T_2$‎ برابر باشد با درختی که از اضافه کردن برگ ‎$l$‎ به درخت ‎$T_1$‎ ساخته می‌شود و بزرگ‌ترین مسیر درخت ‎$T_1$‎ بین دو راس ‎$u$‎ و ‎$v$‎ باشد، بزرگ‌ترین مسیر درخت ‎$T_2$‎ یکی از سه مسیر ‎$(u,v)$‎ ، ‎$(u,l)$‎ و ‎$(v,l)$‎ خواهد بود.

‎ پس اگر ما بتوانیم فاصله هر دو راس ‎$(u,v)$‎ را در زمان ‎${\cal O}(\log n)$‎ به‌دست بیاوریم، می‌توانیم با اضافه کردن هر راس به درخت، بلندترین مسیر آن را در زمان ‎${\cal O}(\log n)$‎ به‌روز کنیم و اندازه آن را چاپ کنیم.

‎ برای این کار ابتدا درخت ‎$T$‎ که شامل تمام ‎$n$‎ راس است را می‌سازیم و درخت را از راس ‎$1$‎ به صورت زیر پیمایش می‌کنیم:

پیمایش راس ‎$u$

  • ‎ $u$‎ را به لیست ‎$l$‎ اضافه کن
  • ‎‎ به‌ازای هر فرزند ‎$v$‎ از راس ‎$u$‎:
    • ‎‎ راس ‎$v$‎ را پیمایش کن
    • ‎ $u$‎ را به لیست ‎$l$‎ اضافه کن

اگر ‎$dep$‎ هر راس برابر با فاصله آن راس از راس شماره ‎$1$‎ باشد، فاصله دو راس ‎$list[i]$‎ و $list[j]$ برابر خواهد بود با:

‎ ‎$$dep[list[i]]‎ + ‎dep[list[j]]‎ - ‎min(dep[list[i]],dep[list[i+1]],\cdots,dep[list[j]])$$‎

‎ پس کافیست به‌ازای هر راس یکی از مکان‌هایی که در لیست قرار دارد را ذخیره کنیم و مقادیر ‎$dep[list[i]]$‎ ها را در یک ‎segment tree‎ ذخیره کنیم تا بتوانیم فاصله هر دو راس را در زمان ‎${\cal O}(\log n)$‎ به‌دست بیاوریم.‎

پیچیدگی: به‌دست آوردن مقادیر ‎$dep$‎ راس‌ها را می‌توان در ‎${\cal O}(n)$‎ انجام داد و فاصله هر دو راس را می‌توان در زمان ‎${\cal O}(\log n)$‎ به‌دست آورد ، هم‌چنین ساختن لیست ‎$l$‎ در زمان ‎${\cal O}(n)$‎ انجام می‌شود. پس کل کار در زمان ‎${\cal O}(n \log n)$‎ انجام می‌شود.


ابزار صفحه