در تاریخ آسیا کشوری به نام Mayo وجود داشته که یکی از قویترین کشورهای زمان خود بوده است.
این کشور در ابتدا شامل تنها یک شهر بوده و آن شهر پایتخت Mayo بوده است. مردم Mayo به مرور زمان با کشورهای همسایه وارد جنگ شدند و هر بار یک کشور را غارت کرده و آن را به عنوان یک شهر جدید به کشور خود اضافه میکردند. همچنین برای این که بتوانند بین تمام شهرهای خود حرکت کنند، یک جاده بین شهر جدید و یکی از شهر های قدیمی احداث میکردند و در صورتی که شهر جدید به اندازه کافی بزرگ میبود، آن شهر را به عنوان پایتخت جدید Mayo انتخاب میکردند.
برای پادشاه Mayo فاصله بقیه شهرها از پایتخت (کمترین تعداد جادههایی که بین هر شهر و پایتخت وجود دارد) بسیار مهم بوده است. برای همین با دادن اطلاعات مربوط به شهرها و جادهها، از شما خواسته شده تا بعد از اضافه شدن هر شهر به Mayo فاصله دورترین شهر از پایتخت 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$
اگر $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)$ انجام میشود.