بخش الف (بدون استقرا)- درخت متناظر با این شهر ها رو میسازیم ( هر شهر یه راس هر جاده یه یال هر عوارض یک وزن ) . توی یک حالت تعیین عوارض ، میگیم راس v <سیاهه> اگر در آمدش با لاقل یکی از مجاور هاش برابر باشه . همینطور واضحه که هیچ برگی نمیتونه راس سیاه باشه ( مگر تو بخش ب که فعلن بهش کاری نداریم )‌

هدف ما اینه که ثابت کنیم حالتی برای تعیین عوارض وجود داره که توش هیچ راسی سیاه نیست !

حالا یک فرم به این درخت میدیم چون قراره بعدن راجبش حرف بزنیم . میایم درخت رو از برگ r ریشه دار میکنیم .
برهان خلف میزنیم و فرض میکنیم تو تمام حالت های تعیین عوارض لاقل یه راس سیاه وجود داره . حالا برای هر حالت میایم عددی رو در نظر میگیرم ، اون عدد برابر شماره ی طبقه ی بالاترین راس سیاهه .

از بین حالات مختلف اونی رو در نظر میگیریم که عددش از همه بیشتره (یعنی بالاترین راس سیاهش از همه پایین تره) .

بالا ترین راس سیاه این حالت به اسم v رو در نظر میگیریم. با اجرای عملیات فوق میتونیم v رو از سیاه بودن بیرون بیاریم . و اگر راس سیاه دیگه ای هم تو همین طبقه بود ، همون عملیاتو براش در نظر میگیریم تا اینکه این طبقه دیگه شامل راس سیاه نباشه که یعنی بالاترین راس سیاه توی یکی از طبقات پایین تره و اونوقت تناقض پیش میاد زیرا یعنی حالتی هست که عددش از حالت فعلی بیشتره ولی گفتیم حالت فعلی بیشترین عدد رو داره پس این به این معنی هست که حتمن حالتی وجود داره که توش هیچ راسی سیاه نیست.

توضیح عملیات : راسv ، مجاور های رو به پایینش (بچه هاش)‌ رو در نظر میگیریم (لاقل یک مجاور رو به پایین داره چون برگ نیست )‌ . از بین این رئوس ، راس u که در آمدش برابر در آمد v هست ، در نظر میگیریم. میدونیم این راس سیاهه . (با توجه به توضیح <سیاه بودن>) از طرفی میدونیم راس سیاه به هیچ وجه برگ نیست ، پس u لاقل یک یال e رو به پایین داره . اگر عوارض اختصاص یافته به e رو تغییر بدیم ،‌در اونصورت در آمد u تغییر میکنه و درآمد v هم ثابت میمونه و در این حالت راس u در آمدش با راس v برابر نیست .
اگر v همچنان سیاه بود یعنی هنوز یکی از بچه هاش به اندازه خودش در آمد داره در اونصورت همین عملیاتو تکرار میکنیم تا زمانی که v دیگه سیاه نباشه.

بخش ب

۶ راس متوالی در نظر میگیریم‌ که یک مسیر را تشکیل میدهند. پیشنهاد کارشناس ها برای عوارض یال های این مسیر به ترتیب از چپ به راست :

۱ و ۲
۰ و ۴
۱۲ و ۱۳
۰ و ۴
۸ و ۷

واضحه که عوارض یال دوم باید ۴ باشد و یال چهارم هم باید ۴ باشد ، که باز هم دو راس وسط درآمدشان با هم برابر میشود.

اول درختو آویزون میکنیم حالا به صورت رندوم یه سری عدد به یالها میدیم

حالا الگوریتمی رو انجام میدیم که هربار راسی که با یکی از رئوس مجاورش عددش یکیه رو؛عددش رو تغییر میدیم ولی ممکنه بچه های اون شهر مشکل پیدا کنن و بد بشن

پس باید ثابت کنیم الگوریتممون پایان پذیره و بلاخره به حالتی میرسیم که هیچ راس بدی نمونه

که اینم میشه گفت یه راس رو در نظر میگیریم مثل i که اولین راسیه که عددش با پدرش یکسانه؛ پس ما میتونیم عدد یال یکی از بچه های i رو تغییر بدیم و همینطور ممکنه یکی از بچه های i بد بشه که این الگوریتمو برای اون انجام میدیم و میگیم چون تهش به برگ میرسیم الگوریتم تموم میشه چون اگه بابای برگ بد بود که عدد یالی که برگ به باباش داره رو عوض میکنیم و چون همچنان عدده + هست عدد پدر با بچش که برگه متفاوته و حل میشه :))

راه حلو نمیگم ولی ایده الفش اینه

درختو ریشه دار کن برگی که بیشترین فاصله رو داره با ریشه رو حذف کن و رو درخت باقی مانده استقرا بزن بعدش برگو برگردون ثابت کن که با یکی از دو تا عدد نوشته شده بر روی یال متصل کنندش با بقیه درخت میشه درخت جدیدی ساخت که این ویژگی رو داره ب شم میتونی با همین راه حل بسازی

حل نشد کل راهو فردا میزارم