پدر‌بزرگ


  • محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت
  • آزمون عملی دوم فاینال سی و دومین دوره المپیاد کامپیوتر ایران

سال گذشته در روز کریسمس، کیومرث یک درخت ریشه‌دار n+1n+1 راسی با شماره‌های 00 تا nn خرید که ریشه‌ی آن راس شماره 00 و پدر راس شماره ii ام، راس با شماره pip_i است. در ابتدا درخت کیومرث به شکل یک مسیر است که درجه راس 00 در آن یک است و روی هر راس تعدادی نامنفی گوی قرار دارد.

کیومرث که از شکل درخت خود ناراضی بود، تصمیم گرفت عملیات زیر را به تعدادی دلخواه روی درختش اعمال کند:

  • کیومرث در یک عملیات می‌تواند راسی دلخواه مانند vv انتخاب کند و پدربزرگش را به عنوان پدرش قرار دهد. به عبارتی pvp_v بعد از انجام عملیات برابر با ppvp_{p_v} قبل از انجام عملیات خواهد شد. همچنین او به هر راس در زیردرخت vv یک گوی اضافه می‌کند. برای انجام عملیات لازم است vv پدربزرگ داشته باشد؛ یعنی ریشه یا فرزند ریشه نباشد.

حال پس از گذشت یکسال، کیومرث درختی در خانه‌اش پیدا کرده که پدر راس‌هایش p1,p2,,pn p_1, p_2, \cdots , p_n\ و تعداد گوی‌هایشان a1,a2,,an a_1, a_2, \cdots , a_n\ می‌باشد. اما می‌خواهد بداند که آیا این درخت همان درخت کریسمس است یا خیر. جواب سوال او تنها در صورتی مثبت است که بتوان با شروع از درختی به شکل مسیر و اعمال تعدادی عملیات بر روی آن، به همین درخت برسیم. همچنین در صورت مثبت بودن جواب، مسیری را می‌خواهد پیدا کند که اگر راس‌های آن را به‌ترتیب از ریشه تا آخر بنویسیم، لکسیکوگرافیکالی کمینه باشد.

در این سوال شما باید در QQ سناریو مختلف، به کیومرث کمک کنید. در هر سناریو باید اعداد nn و TT و p1,p2,,pn p_1, p_2, \cdots , p_n\ و a1,a2,,an a_1, a_2, \cdots , a_n\ را ورودی بگیرید، سپس تعیین کنید که آیا مسیر اولیه‌ای وجود دارد یا نه، و در نهایت اگر T=1T = 1 بود، مسیر مورد نظر را هم خروجی دهید.

ورودی🔗

در خط اول ورودی تعداد سناریو ها QQ می‌آید.

در هر سناریو در خط اول، دو عدد nn و TT به ترتیب و با فاصله از هم آمده‌اند.

در هر یک از nn خط بعدی، دو عدد طبیعی pip_i و aia_i به‌ترتیب می‌آیند.

خروجی🔗

به ازای هر سناریو اگر مسیری وجود داشت، عبارت Yes و در غیر این صورت، عبارت No را چاپ کنید. سپس اگر T=1T = 1 بود، راس‌های مسیر را به ترتیب و با فاصله از هم چاپ کنید. خروجی شما باید جایگشتی از اعداد 11 تا nn باشد و خود ریشه را شامل نمی‌شود. دقت کنید که اگر T=0T = 0 بود، شما نباید هیچ خروجی دیگری بدهید!

محدودیت‌ها🔗

1Q3000001 \leq Q \leq 300 \, 000 1n3000001 \leq n \leq 300 \, 000 T{0,1}T \in \{ 0, 1 \} 0pi<i0 \leq p_i < i 1ai1091 \leq a_i \leq 10^9

  • جمع مقادیر nn به ازای تمام سناریوها از 300000300 \, 000 بیشتر نمی‌شود.

زیرمسئله‌ها🔗

زیرمسئله نمره محدودیت
۱ ۱۲ T=0T = 0 و pi=0p_i = 0 به ازای تمامی ii ها برقرار است.
۲ ۱۵ T=1T = 1 و pi=0p_i = 0 به ازای تمامی ii ها برقرار است.
۳ ۴۱ T=0T = 0
۴ ۳۲ T=1T = 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
Plain text

خروجی نمونه ۱🔗

Yes
Yes
1 3 2 4
No
Yes
1 2 4 3
Plain text

شوالیه تاریکی


  • محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت
  • آزمون عملی دوم فاینال سی و دومین دوره المپیاد کامپیوتر ایران

‌ا Scarecrow به گاتهام آمده و مردم شهر را مسموم کرده است. Batman با کمک دستیارانش توانسته پادزهری بسازد که مردم را شفا بدهد و حالا می‌خواهد آن را بین مردم پخش کند. نقشه شهر گاتهام به صورت یک درخت nn راسی می‌باشد که هر راس از آن یک منطقه را نشان می‌دهد. بتمن یک منطقه مانند vv را انتخاب می‌کند و پادزهر را از آن منطقه منتشر می‌کند. بتمن با افسر گوردن هماهنگ کرده است تا دقیقا یکی از جاده‌ها (یال) را غیر قابل عبور کند تا اهالی منطقه vv نتوانند از فاصله kk این منطقه دورتر بروند زیرا اگر بتوانند خود را به منطقه‌ای برسانند که فاصله آن با vv حداقل kk جاده باشد، پادزهر روی آن‌ها اثر نمی‌کند.

به همین خاطر افسر گوردن از بتمن می‌خواهد تا تعداد جاده‌هایی که با بسته شدن آن‌ها پادزهر اثر نمی‌کند را به او بگوید. بتمن که هنوز راس اولیه و مقدار kk را انتخاب نکرده است، از شما کمک می‌خواهد تا این تعداد را به ازای QQ سناریو مختلف جواب دهید.

ورودی🔗

در خط اول دو عدد طبیعی nn تعداد مناطق گاتهام و qq تعداد سناریوها به‌ترتیب می‌آیند.

در خط بعدی دنباله p2,p3,,pn p_2, p_3, \cdots, p_{n}\ می‌آیند. به ازای هر 2in2 \leq i \leq n جاده‌ای میان دو منطقه ii و pip_i وجود دارد.

در هر یک از qq خط بعدی، دو عدد طبیعی viv_i و kik_i می‌آیند.

خروجی🔗

در qq خط جواب مربوط به هر سناریو را چاپ کنید.

محدودیت‌ها🔗

1n,q3000001 \leq n, q \leq 300 \, 000 1pii11 \leq p_i \leq i - 1 1vi,kin1 \leq v_i, k_i \leq n

زیرمسئله‌ها🔗

زیرمسئله نمره محدودیت
۱ ۸ pi=i1p_i = i-1 به ازای تمامی 2in2 \leq i \leq n برقرار است.
۲ ۱۳ n300n \leq 300 و q1000q \leq 1000
۳ ۲۲ n,q1000n, q\leq 1000
۴ ۱۸ n,q100000n, q \leq 100 \, 000 و فاصله منطقه 11 با دورترین منطقه از آن حداکثر 4040 جاده می‌باشد.
۵ ۲۸ n,q100000n, q \leq 100 \, 000
۶ ۱۱ بدون محدودیت اضافی

مثال🔗

ورودی نمونه ۱🔗

5 5
1 1 3 4
1 2
4 1
2 1
2 2
3 3
Plain text

خروجی نمونه ۱🔗

2
4
3
2
0
Plain text

ورودی نمونه ۲🔗

10 1
1 2 3 4 5 4 7 6 9
8 5
Plain text

خروجی نمونه ۲🔗

7
Plain text

گراف ورودی دوم به شکل زیر است.

سمپل ۲
شکل ۱: شکل گراف نمونه ورودی ۲

اگر افسر گوردن هر جاده‌ای به جز جاده‌های بین 4,7\langle 4, 7 \rangle یا 7,8\langle 7, 8 \rangle را ببندد، مردم می‌توانند از منطقه 88 به حداقل یکی از مناطق 11 یا 99 بروند و پادزهر روی آن‌ها اثر نگذارد.

گاو‌صندوق


  • محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت
  • آزمون عملی دوم فاینال سی و دومین دوره المپیاد کامپیوتر ایران

علی‌جان گاوصندوق هوشمندی دارد که رمز آن را فراموش کرده است. او می‌داند رمز گاوصندوقش جایگشتی از اعداد 11 تا nn می‌باشد. علی‌جان از گاوصندوق هوشمند راهنمایی می‌گیرد تا رمز را پیدا کند. اگر رمز گاوصندوق جایگشت s=s1,s2,,sn s = \langle s_1, s_2, \cdots, s_n \rangle\ باشد، ابتدا عملیات زیر را انجام می‌دهد، و سپس جایگشت نهایی را به علی‌جان می‌دهد.

شبه‌کد

علی‌جان مقدار kk و جایگشت بعد از اجرا شدن کد بالا روی آن را دارد. او می‌خواهد بداند چند دنباله مختلف ممکن است رمز گاوصندوقش باشد.

ورودی🔗

در خط اول ورودی دو عدد طبیعی nn و سپس kk به‌ترتیب می‌آیند.

در خط دوم ورودی nn عدد s1,s2,,sn s_1, s_2, \cdots, s_n\ به‌ترتیب می‌آیند.

خروجی🔗

در تنها خط خروجی، تعداد دنباله‌های مختلفی که می‌توانند رمز گاوصندوق باشند را چاپ کنید. از آنجایی که این مقدار ممکن است بزرگ باشد، باقی‌مانده تقسیم آن بر 109+710^9+7 را چاپ کنید.

محدودیت‌ها🔗

2n,k2000002 \leq n, k \leq 200 \, 000 1sin1 \leq s_i \leq n

  • شرط sisjs_i \neq s_j به ازای تمامی iji \neq j برقرار می‌باشد.

زیرمسئله‌ها🔗

زیرمسئله نمره محدودیت
۱ ۱۰ n15n \leq 15
۲ ۲۱ k=1k = 1
۳ ۲۹ k=2k = 2 و n2000n \leq 2000
۴ ۱۷ k50 k \leq 50
۵ ۲۳ بدون محدودیت اضافی

مثال🔗

ورودی نمونه ۱🔗

4 1
1 2 3 4
Plain text

خروجی نمونه ۱🔗

8
Plain text

ورودی نمونه ۲🔗

6 2
5 1 3 4 2 6
Plain text

خروجی نمونه ۲🔗

2
Plain text

جایگشت 3,5,1,6,4,2 \langle 3, 5, 1, 6, 4, 2 \rangle\ یکی از جایگشت‌هایی است که ممکن است رمز گاوصندوق دوم باشد. عملیات‌هایی که روی این جایگشت انجام می‌شود:

  1. در مرحله اول، s1>min(s2,s3) s_1 > \min(s_2, s_3)\ می‌باشد، پس جابه‌جایی انجام می‌دهد و به جایگشت 5,3,1,6,4,2\langle 5, 3, 1, 6, 4, 2 \rangle تبدیل می‌شود.
  2. در مرحله دوم، s2>min(s3,s4)s_2 > \min(s_3, s_4) می‌باشد، پس جابه‌جایی انجام می‌دهد و به جایگشت 5,1,3,6,4,2\langle 5, 1, 3, 6, 4, 2 \rangle تبدیل می‌شود.
  3. در این مرحله جابه‌جایی انجام نمی‌دهد.
  4. در این مرحله مجددا جابه‌جایی انجام می‌دهد و به جایگشت 5,1,3,4,6,2\langle 5, 1, 3, 4, 6, 2 \rangle تبدیل می‌شود.
  5. در مرحله آخر نیز جابه‌جایی انجام می‌شود و به جایگشت نهایی 5,1,3,4,2,6\langle 5, 1, 3, 4, 2, 6 \rangle تبدیل می‌شود.