درخت پالتی

یک درخت ریشه‌دار داریم که ریشه‌ی آن راس ۱ است. به تعدادی از رئوس این درخت «راس کامکار» می‌گوییم. می‌خواهیم از بین بچه‌های هرکدام از راس‌های کامکار دقیقاً یکی از آن‌ها را انتخاب کرده و کل زیردرخت بقیه‌ی بچه‌های آن را از درخت حذف کنیم. سپس بچه‌های هرکدام از رئوس درختی که پس از انجام این عملیات به ازای تمام رئوس کامکار درخت باقی می‌ماند (در درخت حاصل، هر راس کامکار در درخت اولیه [به شرط برگ نبودن] دقیقاً یک بچه دارد) را به ترتیب از کوچک به بزرگ مرتب می‌کنیم و دنباله‌ی پیش‌نویس آن را می‌نویسیم. برای فهم بیشتر به مثال زیر توجه کنید:

در این شکل، رئوس تیره همان رئوس کامکار هستند؛ اگر برای راس شماره‌ی ۹، راس شماره‌ی ۲۶ را انتخاب کنیم، کل زیردرخت راس‌های ۴ و ۷ از بین خواهد رفت. توجه کنید که در این صورت دیگر نیازی نیست از بین بچه‌های راس شماره‌ی ۷ یکی را انتخاب کنیم، زیرا حذف شده است!

برای مثال یکی از درختانی که در نهایت می‌توان به آن رسید، شکل زیر است که با انتخاب رئوس $\langle7,8,19,21\rangle$ و حذف زیردرخت رئوس $\langle2,3,4,16,22,22\rangle$ درست شده است که پس از مرتب کردن بچه‌های هر راس و نوشتن دنباله‌ی پیش‌نویس آن، به دنباله‌ی $\langle1,9,7,19,15,21,14,17,5,8,6,10,11,18\rangle$ می‌رسیم و گراف آن نیز به شکل زیر در می‌آید:

ورودی

یال‌های درخت ۱۴۰۱۴۰۱ راسی $T$ که ۲۰۲۰۲۲ راس کامکار دارد در یک فایل به نام tree.in به شما داده شده است. در خط $i$ ام از ۱۴۰۱۴۰۰ خط اول، دو راس $u_i$ و $v_i$ که دو سر یال $i$ ام درخت هستند آمده است و در ۲۰۲۰۲۲ خط بعدی، شماره‌ی راس‌های کامکار درخت نوشته شده‌اند.

تمام پاسخ‌های ارائه شده در این سوال با فرض $\Delta = 10256483$ محاسبه شده‌اند.

$2$- الف ($25$ نمره) : یک درخت دودویی کامل¹⁾ به ارتفاع ۱۴۰۱ داریم که راس‌های آن از بالا به پایین و در هر ارتفاع از چپ به راست شماره‌گذاری شده‌اند. اگر راس‌های با شماره‌ی زوج در این درخت، راس‌های کامکار باشند تعداد دنباله‌های مختلف که می‌توان به آن‌ها رسید به پیمانه‌ی $\Delta$ چقدر است؟

$2$- ب ($25$ نمره) : بین تمام دنباله‌هایی که از روی درخت $T$ می‌توان ساخت، کوچک‌ترین آن‌ها را بر حسب ترتیب لغت‌نامه‌ای²⁾ یادداشت می‌کنیم. اگر عدد ۱۴۰۱ ام این دنباله برابر $u$ باشد، باقی‌مانده‌ی تقسیم $u^3$ به پیمانه‌ی $\Delta$ چقدر است؟

$2$- ج ($25$ نمره) : تعداد دنباله‌های مختلفی که از روی درخت $T$ می‌توان ساخت به پیمانه‌ی $\Delta$ چقدر است؟

$2$- د ($25$ نمره) : تمام دنباله‌های مختلفی که از روی درخت $T$ می‌توان ساخت را پشت سر هم نوشته‌ایم و به دنباله‌ای به طول $k$ رسیده‌ایم. باقی‌مانده‌ی تقسیم عدد $k^\Delta$ بر $\Delta$ چقدر است؟