+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت + آزمون عملی دوم فاینال سی و دومین دوره المپیاد کامپیوتر ایران ---------- سال گذشته در روز کریسمس، کیومرث یک درخت ریشه‌دار $n+1$ راسی با شماره‌های $0$ تا $n$ خرید که ریشه‌ی آن راس شماره $0$ و پدر راس شماره $i$ ام، راس با شماره $p_i$ است. در ابتدا درخت کیومرث به شکل یک مسیر است که درجه راس $0$ در آن یک است و روی هر راس تعدادی نامنفی گوی قرار دارد. کیومرث که از شکل درخت خود ناراضی بود، تصمیم گرفت عملیات زیر را به تعدادی دلخواه روی درختش اعمال کند: + کیومرث در یک عملیات می‌تواند راسی دلخواه مانند $v$ انتخاب کند و پدربزرگش را به عنوان پدرش قرار دهد. به عبارتی $p_v$ بعد از انجام عملیات برابر با $p_{p_v}$ قبل از انجام عملیات خواهد شد. همچنین او به هر راس در زیردرخت $v$ یک گوی اضافه می‌کند. برای انجام عملیات لازم است $v$ پدربزرگ داشته باشد؛ یعنی ریشه یا فرزند ریشه نباشد. حال پس از گذشت یکسال، کیومرث درختی در خانه‌اش پیدا کرده که پدر راس‌هایش $p_1, p_2, \cdots , p_n\ $ و تعداد گوی‌هایشان $a_1, a_2, \cdots , a_n\ $ می‌باشد. اما می‌خواهد بداند که آیا این درخت همان درخت کریسمس است یا خیر. جواب سوال او تنها در صورتی مثبت است که بتوان با شروع از درختی به شکل مسیر و اعمال تعدادی عملیات بر روی آن، به همین درخت برسیم. همچنین در صورت مثبت بودن جواب، مسیری را می‌خواهد پیدا کند که اگر راس‌های آن را به‌ترتیب از ریشه تا آخر بنویسیم، لکسیکوگرافیکالی کمینه باشد. در این سوال شما باید در $Q$ سناریو مختلف، به کیومرث کمک کنید. در هر سناریو باید اعداد $n$ و $T$ و $p_1, p_2, \cdots , p_n\ $ و $a_1, a_2, \cdots , a_n\ $ را ورودی بگیرید، سپس تعیین کنید که آیا مسیر اولیه‌ای وجود دارد یا نه، و در نهایت اگر $T = 1$ بود، مسیر مورد نظر را هم خروجی دهید. # ورودی در خط اول ورودی تعداد سناریو ها $Q$ می‌آید. در هر سناریو در خط اول، دو عدد $n$ و $T$ به ترتیب و با فاصله از هم آمده‌اند. در هر یک از $n$ خط بعدی، دو عدد طبیعی $p_i$ و $a_i$ به‌ترتیب می‌آیند. # خروجی به ازای هر سناریو اگر مسیری وجود داشت، عبارت ```Yes``` و در غیر این صورت، عبارت ```No``` را چاپ کنید. سپس اگر $T = 1$ بود، راس‌های مسیر را به ترتیب و با فاصله از هم چاپ کنید. خروجی شما باید جایگشتی از اعداد $1$ تا $n$ باشد و خود ریشه را شامل نمی‌شود. دقت کنید که اگر $T = 0$ بود، شما نباید هیچ خروجی دیگری بدهید! # محدودیت‌ها $$1 \leq Q \leq 300 \, 000$$ $$1 \leq n \leq 300 \, 000$$ $$T \in \{ 0, 1 \}$$ $$0 \leq p_i < i$$ $$1 \leq a_i \leq 10^9$$ + جمع مقادیر $n$ به ازای تمام سناریوها از $300 \, 000$ بیشتر نمی‌شود. # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت |:------------------:|:----------:|:------------------:| | ۱ | ۱۲ | $T = 0$ و $p_i = 0$ به ازای تمامی $i$ ها برقرار است. | | ۲ | ۱۵ | $T = 1$ و $p_i = 0$ به ازای تمامی $i$ ها برقرار است. | | ۳ | ۴۱ | $T = 0$ | | ۴ | ۳۲ | $T = 1$ | # مثال ## ورودی نمونه ۱ ``` 4 1 0 0 0 4 1 0 2 0 3 0 1 0 4 4 1 0 0 1 0 2 0 2 0 4 1 0 0 1 0 2 1 2 0 ``` ## خروجی نمونه ۱ ``` Yes Yes 1 3 2 4 No Yes 1 2 4 3 ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت + آزمون عملی دوم فاینال سی و دومین دوره المپیاد کامپیوتر ایران ---------- ‌ا Scarecrow به گاتهام آمده و مردم شهر را مسموم کرده است. Batman با کمک دستیارانش توانسته پادزهری بسازد که مردم را شفا بدهد و حالا می‌خواهد آن را بین مردم پخش کند. نقشه شهر گاتهام به صورت یک درخت $n$ راسی می‌باشد که هر راس از آن یک منطقه را نشان می‌دهد. بتمن یک منطقه مانند $v$ را انتخاب می‌کند و پادزهر را از آن منطقه منتشر می‌کند. بتمن با افسر گوردن هماهنگ کرده است تا دقیقا یکی از جاده‌ها (یال) را غیر قابل عبور کند تا اهالی منطقه $v$ نتوانند از فاصله $k$ این منطقه دورتر بروند زیرا اگر بتوانند خود را به منطقه‌ای برسانند که فاصله آن با $v$ حداقل $k$ جاده باشد، پادزهر روی آن‌ها اثر نمی‌کند. به همین خاطر افسر گوردن از بتمن می‌خواهد تا تعداد جاده‌هایی که با بسته شدن آن‌ها پادزهر اثر **نمی‌کند** را به او بگوید. بتمن که هنوز راس اولیه و مقدار $k$ را انتخاب نکرده است، از شما کمک می‌خواهد تا این تعداد را به ازای $Q$ سناریو مختلف جواب دهید. # ورودی در خط اول دو عدد طبیعی $n$ تعداد مناطق گاتهام و $q$ تعداد سناریوها به‌ترتیب می‌آیند. در خط بعدی دنباله $p_2, p_3, \cdots, p_{n}\ $ می‌آیند. به ازای هر $2 \leq i \leq n$ جاده‌ای میان دو منطقه $i$ و $p_i$ وجود دارد. در هر یک از $q$ خط بعدی، دو عدد طبیعی $v_i$ و $k_i$ می‌آیند. # خروجی در $q$ خط جواب مربوط به هر سناریو را چاپ کنید. # محدودیت‌ها $$1 \leq n, q \leq 300 \, 000$$ $$1 \leq p_i \leq i - 1$$ $$1 \leq v_i, k_i \leq n$$ # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت |:------------------:|:----------:|:------------------:| | ۱ | ۸ | $p_i = i-1$ به ازای تمامی $2 \leq i \leq n$ برقرار است. | | ۲ | ۱۳ | $n \leq 300$ و $q \leq 1000$ | | ۳ | ۲۲ | $n, q\leq 1000$ | | ۴ | ۱۸ | $n, q \leq 100 \, 000$ و فاصله منطقه $1$ با دورترین منطقه از آن حداکثر $40$ جاده می‌باشد. | | ۵ | ۲۸ | $n, q \leq 100 \, 000$ | | ۶ | ۱۱ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 5 5 1 1 3 4 1 2 4 1 2 1 2 2 3 3 ``` ## خروجی نمونه ۱ ``` 2 4 3 2 0 ``` ## ورودی نمونه ۲ ``` 10 1 1 2 3 4 5 4 7 6 9 8 5 ``` ## خروجی نمونه ۲ ``` 7 ``` گراف ورودی دوم به شکل زیر است. |  | |:--------:| | شکل ۱: شکل گراف نمونه ورودی ۲ | اگر افسر گوردن هر جاده‌ای به جز جاده‌های بین $\langle 4, 7 \rangle$ یا $\langle 7, 8 \rangle$ را ببندد، مردم می‌توانند از منطقه $8$ به حداقل یکی از مناطق $1$ یا $9$ بروند و پادزهر روی آن‌ها اثر نگذارد.

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت + آزمون عملی دوم فاینال سی و دومین دوره المپیاد کامپیوتر ایران ---------- علی‌جان گاوصندوق هوشمندی دارد که رمز آن را فراموش کرده است. او می‌داند رمز گاوصندوقش جایگشتی از اعداد $1$ تا $n$ می‌باشد. علی‌جان از گاوصندوق هوشمند راهنمایی می‌گیرد تا رمز را پیدا کند. اگر رمز گاوصندوق جایگشت $s = \langle s_1, s_2, \cdots, s_n \rangle\ $ باشد، ابتدا عملیات زیر را انجام می‌دهد، و سپس جایگشت نهایی را به علی‌جان می‌دهد.  علی‌جان مقدار $k$ و جایگشت بعد از اجرا شدن کد بالا روی آن را دارد. او می‌خواهد بداند چند دنباله مختلف ممکن است رمز گاوصندوقش باشد. # ورودی در خط اول ورودی دو عدد طبیعی $n$ و سپس $k$ به‌ترتیب می‌آیند. در خط دوم ورودی $n$ عدد $s_1, s_2, \cdots, s_n\ $ به‌ترتیب می‌آیند. # خروجی در تنها خط خروجی، تعداد دنباله‌های مختلفی که می‌توانند رمز گاوصندوق باشند را چاپ کنید. از آنجایی که این مقدار ممکن است بزرگ باشد، باقی‌مانده تقسیم آن بر $10^9+7$ را چاپ کنید. # محدودیت‌ها $$2 \leq n, k \leq 200 \, 000$$ $$1 \leq s_i \leq n$$ + شرط $s_i \neq s_j$ به ازای تمامی $i \neq j$ برقرار می‌باشد. # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت |:------------------:|:----------:|:------------------:| | ۱ | ۱۰ | $n \leq 15$ | | ۲ | ۲۱ | $k = 1$ | | ۳ | ۲۹ | $k = 2$ و $n \leq 2000$ | | ۴ | ۱۷ | $ k \leq 50$ | | ۵ | ۲۳ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 4 1 1 2 3 4 ``` ## خروجی نمونه ۱ ``` 8 ``` ## ورودی نمونه ۲ ``` 6 2 5 1 3 4 2 6 ``` ## خروجی نمونه ۲ ``` 2 ``` جایگشت $\langle 3, 5, 1, 6, 4, 2 \rangle\ $ یکی از جایگشت‌هایی است که ممکن است رمز گاوصندوق دوم باشد. عملیات‌هایی که روی این جایگشت انجام می‌شود: 1. در مرحله اول، $s_1 > \min(s_2, s_3)\ $ می‌باشد، پس جابه‌جایی انجام می‌دهد و به جایگشت $\langle 5, 3, 1, 6, 4, 2 \rangle$ تبدیل می‌شود. 2. در مرحله دوم، $s_2 > \min(s_3, s_4)$ می‌باشد، پس جابه‌جایی انجام می‌دهد و به جایگشت $\langle 5, 1, 3, 6, 4, 2 \rangle$ تبدیل می‌شود. 3. در این مرحله جابه‌جایی انجام نمی‌دهد. 4. در این مرحله مجددا جابه‌جایی انجام می‌دهد و به جایگشت $\langle 5, 1, 3, 4, 6, 2 \rangle$ تبدیل می‌شود. 5. در مرحله آخر نیز جابه‌جایی انجام می‌شود و به جایگشت نهایی $\langle 5, 1, 3, 4, 2, 6 \rangle$ تبدیل می‌شود.