برای الف که جواب دادن برای ب اول با درخت پوشا بی اف از اون راس r اثبات میکنی که همش یه طبقه میری پایین و برای حداقل بودنش من اول یه درخت دودوییه کامل

$$ 2^(r+1)-1 $$

راسی کشیدم و گفتم با درخت تصمیم و قضیه مرکز درخت نتیجه میگریم که log این یعنی r تا مرحله نیازه

دوستان من دو تا سوتی دادم نمره منو حدس بزنید دیگه الفش رو من بدست اوردم ولی مکس ننوشتم گفتم اگه تو استان i با شه این.... یکیم تو ب fr>=r رو برای درخت دودیی نوشتم بعد برای این که بگم همیشه میشه دقیقا اینو گفتم با شروع از راس موردنظر می توان در هر حرکت یک واحد به بمب نزدیک شد و یک شهر مانده به بمب جایگاه بمب مشخص می شود و این که توی fr>=r به جای k,r گرفتم حکمرو برای k یعنی fk>=k ثابت کردم بقیمم درست حالا بگید چند می گیرم

این سوال بخش الف و بش ماس ماس !
برای الفش باید میگفتیم تویه مسیر به طول k که توی یک راسش بمب هست باید حداقل لاگ k بار از دستگاه استفاده کرد. تا بمب به طور تضمینی پیدا بشه
بعد توی مساله اصلی ابتدا دستگاهو تو پایتخت قرار میدیم و دستگاه بهمون میگه بمب تو کدوم استانه و طبق اینکه کدوم شهر از استان انتخاب شده میشه فهمید بمب تو کدوم نیمه ی یک استانه (هر استان دو نیمه داره دیگه !) و هر نیمه ، یک مسیر به طول نصف شهر های اون استانه و با کمک لم ۱ قضیه حله .

):

برای الف و ب که دوستان جواب دادند و منم فکر کنم درسته...ولی برای ج من خودم برهان خلف کردم :)یه دو صفحه و نیمی طول کشید ولی اگر وسطش جوب نزنی و درست جلو بریم فکر نکنم ااشتباه باشه ....

اولیش که باید از بین ai ها ماکزیممش رو در میاوردی، یه باینری میزدی میشد کف log ai +1، دومی هم f(r)=r، سومی هم نتونستم، فقط برای اینکه شاید یه نمره ای بگیرم گفتم رو گراف bfs میزنیم، بعد cemteroid درخت bfs رو پیدا میکنیم و گراف رو هی نصف میکنیم با استفاده از دستگاه بمب یاب در راس centeroid