====== 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)$‎ انجام می‌شود. * [[سوال ۴۷|سوال بعد]] * [[سوال ۴۵|سوال قبل]]