- محدودیت زمان: ۲ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
سازمان اطلاعاتی KGB به دنبال پیشبرد عملیاتی سری است. متاسفانه این سازمان تعدادی از عوامل شریف کوئرا را گروگان گرفته است و تاکید کرده تنها در صورتی آن‌ها را آزاد می‌کند که مسئله‌ای که فرستاده‌اند برای آن‌ها حل شود. نکته‌ی هولناک ماجرا این است که سازمان به ازای هر باری که پاسخ نادرستی برای این مسئله ارسال شود، عضو جدیدی از بدن یکی از عوامل تحت گروگان را قطع و از طریق پست برای کوئرا ارسال می‌کند. متن نامه‌ای که سوال در آن آمده است و ترجمه آن بدون دخل و تصرفی در ادامه آمده است.
کوئرای عزیز،
به یک درخت ریشه‌دار، درخت دودویی می‌گوییم اگر و تنها اگر هر راس آن دقیقا ۰ یا ۲ بچه (یک بچه‌ی چپ و یک بچه‌ی راست) داشته باشد.
به یک درخت ریشه‌دار، درخت دودویی کامل می‌گوییم اگر و تنها اگر دودویی باشد و ارتفاع تمامی برگ‌ها در آن برابر باشد.
به یک درخت ریشه دار، درخت جستجوی دودویی کامل می‌گوییم اگر و تنها اگر درخت دودویی کامل باشد و به ازای هر راس مانند $v$ تمامی راس‌های واقع در زیردرخت چپ $v$ کوچکتر از $v$، و تمامی راس‌های واقع در زیر درخت راست $v$ بزرگتر از $v$ باشند.
حال یک درخت به شما داده شده و ریشه آن مشخص شده است، باید بگویید اندازه بزرگترین زیرمجموعه از راس‌های آن، به طوری که همبند باشند و تشکیل یک زیردرخت به شکل درخت جستجوی دودویی کامل بدهد را چاپ کنید. دقت کنید رابطه پدر فرزندی راس‌ها در درخت اولیه و زیردرخت انتخابی حفظ می‌شوند، به عبارت دیگر ریشه‌ی زیردرخت انتخابی حتما بالاترین راس آن خواهد بود.
با احترام، کا. گ. ب.
ورودی
در خط اول ورودی دو عدد $n$ و ریشه‌ی درخت داده شده است.
در $n-1$ خط بعدی، یال‌های درخت داده شده اند.
$$1 \le n \le 5 \times 10^5$$
خروجی
در تنها خط خروجی، باید اندازه بزرگترین زیردرخت جستجوی دودویی ممکن چاپ شود.
مثال
ورودی نمونه ۱
1 1
خروجی نمونه ۱
1
ورودی نمونه ۲
3 2
1 2
2 3
خروجی نمونه ۲
3
ورودی نمونه ۳
9 5
5 3
5 7
5 8
3 1
3 4
7 2
7 6
7 9
خروجی نمونه ۳
7
ورودی نمونه ۴
15 8
8 4
8 12
4 2
2 1
2 3
4 6
6 5
6 7
12 10
10 9
10 11
12 14
14 13
14 15
خروجی نمونه ۴
15
ارسال پاسخ برای این سؤال