خیکوله به تازگی بازی «Persian Empire» را خریده است. این بازی از نوع استراتژیک است و در ابتدای آن یک نقشه از ایران باستان داده می‌شود که بازی در آن انجام می‌شود. این نقشه یک درخت $|V|$ راسی است که هر راس معادل یک شهر و هر یال معادل یک جاده است.

برای تشکیل امپراطوری خیکوله باید شهر‌ها را استان‌بندی کند. استان‌بندی کردن شهرها باید مطابق با دو قانون زیر باشد:

1. هر شهر دقیقا در یک استان قرار بگیرد.
2. هر دو شهری که در یک استان قرار دارند،‌ با استفاده از جاده‌هایی که کاملا در آن استان قرار دارد، به هم راه داشته باشند.

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

اگر تعداد استان‌ها را برابر با $k$ و ماکسیمم قطر بین همه‌ی استان‌ها را برابر با $d$ در نظر بگیریم، خیکوله می‌خواهد استان‌بندی را طوری انجام دهد تا $Max(k,d)$ مینیمم شود.

الگوریتمی با پیچدگی زمان اجرای $O(|V |log|V|)$ برای یافتن استان بندی بهینه ارائه کنید.

• سوال بعد
• سوال قبل