قسمت الف:

• قرارداد: توی درخت بیتا، یه راس دو شاخه ی ساده مث A رو در نظر بگیرید که دو فرزند به نام B , C داره. طبق تعاریف سوال، می شه راحت فهمید که زیر درخت هر یک از B و C یه درخت مسیره(حتی ممکنه هرکدوم از این دو راس، برگ باشن!). حالا من می یام به ازای تمام رئوس دوشاخه ی ساده ی A، تمام رئوس زیردرختش به جز B و C رو حذف می کنم. بدین ترتیب به درختی می رسم که تمام رئوس دو شاخه ی سادش پدر دوتا برگ هستن که منطقا یکی از اون برگ ها رنگیه! همچنین می یام ریشه رو هم حذف می کنم و درخت حاصل رو بوتی می نامم( دقت کنید که ریشه ی درخت بیتا درجه اش یک بوده).
• نکته: در درخت بوتی، به ازای هر راس رنگی (که منطقا برگه)، لااقل یک برگ رنگ نشده وجود دارد (واضحه!). پس اگه درخت بوتی n برگ داشته باشه، حداکثر کف n/2 تا راس رنگی داره.
• لم# : در هر ریشه دار درخت دودویی n راسی، حداکثر سقف n/2 تا برگ وجود دارد (اثبات با استقرا و به عهده ی خوانند!)
• نتیجه: با توجه به لم#، درخت بوتی که حداکثر 1402 راس داره، حداکثر 701 تا برگ داره و طبق نکته، حداکثر 701/2=350 راس رنگی داره.

حالا وقتی رئوس حذف شده ی درخت بیتا رو به درخت بوتی برگردونیم، تعداد رئوس رنگی بدون احتساب ریشه ثابت می مونه (واضحه به مولا)؛ پس چون ثابت کردیم که در درخت بوتی حداکثر 350 راس رنگی وجود داره، نتیجه می گیریم که درخت بیتا با احتساب ریشه حداکثر 351=1+350 راس رنگی داره.

• قسمت ج: ساختار درختمون باید همانند شکل زیر باشه 👇👇👇

اثبات: از اونجایی که ما حداکثر 350 راس واسه پرسش می دیم و در ضمن، درخت ما 351 بخش داره، پس بخشی وجود داره که هیچ کدوم از راس هاش برای پرسش داده نشدن. فرض کنید بخش i چنین ویژگی ای داشته باشه؛ پس منطقا هیچ یک از رئوس $a_i$ و $b_i$ برای پرسش داده نشدن. حالا اگه راس انتخابی البرز، یکی از این دو راس باشند، بیتا به طور یکتا نمی تواند تشخیص بدهد که کدامشان راس انتخابی البرز است.

توجه کنید که به جز خودِ $a_i$ و $b_i$، به ازای هر راس دیگر در درخت، فاصله اش تا این دو راس، یکسان است.