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

کیومرث یک درخت $n$ راسی جهت‌دار دارد که راس‌‌های آن شماره‌های $1$ تا $n$ دارند و روی راس $i$ام $a_i$ تا نخود قرار دارد. او پس از انجام تعدادی عملیات که در ادامه تعریف می‌شود، به درختی می‌رسد که روی راس $i$ام $b_i$ تا نخود وجود دارد.

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

در این سوال شما باید پس از ورودی گرفتن درخت به همراه دنباله‌ی $a$ و $b$ تعیین کنید آیا می‌توان با انجام دادن تعدادی عملیات، از دنباله‌ی $a$ به دنباله‌ی $b$ رسید یا خیر. همچنین برخی از $b_i$ ها در ورودی نامعلوم هستند؛ به این معنی که آن راس می‌تواند در نهایت هر تعدادی نخود داشته باشد. در هر ورودی باید سوال را به ازای $T$ سناریوی مختلف حل کنید.

ورودی🔗

در خط اول، تعداد سناریوها $T$ می‌آید. $1 \leq T \leq 200 \, 000$

به ازای هر سناریو، در خط اول $n$ تعداد راس‌های درخت می‌آید. $1 \leq n \leq 200 \, 000$

در $i$امین خط از $n$ خط بعدی، دو عدد $a_i$ و $b_i$ به‌ترتیب می‌آیند که تعداد نخود‌های اولیه و تعداد نخود‌های نهایی راس $i$ام را نشان می‌دهد (اگر $b_i = -1$ باشد، تعداد نخود‌های این راس نامعلوم است).

$-1 \leq b_i \leq 10^{12}, \quad 0 \leq a_i \leq 10^{12}$

در $n - 1$ خط بعدی در هر خط دو عدد $v$ و $u$ به ‌ترتیب می‌آیند که نشان‌دهنده‌ی یالی جهت‌دار از $v$ به $u$ می‌باشد. تضمین می‌شود بدون در نظر گرفتن جهت یال‌ها، یک درخت تشکیل می‌دهند.

$1 \leq v, u \leq n$

تضمین می‌شود مجموع $n$ به ازای تمام سناریوها از $200 \,000$ بیشتر نمی‌شود.

خروجی🔗

خروجی شامل $T$ خط است که در هر خط اگر با صرف نظر از $b_i$های نامعلوم می‌توان به دنباله‌ی $b$ رسید، عبارت Yes و در غیر این صورت عبارت No را چاپ کنید.

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

مثال‌ها🔗

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

3
2
5 7
5 -1
1 2
5
1 -1
4 -1
1 1
5 0
5 -1
1 5
3 1
5 4
1 2
5
4 -1
5 1
5 -1
3 3
0 -1
1 3
2 1
4 2
2 5

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

No
No
Yes

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

امیر و مهدی برای گردش به جنگل تصادفی رفته‌اند که درختان این جنگل توجه آنها را جلب می‌کند. آن‌ها برای آشنایی بیشتر با این درختان به اعماق جنگل می‌روند اما بعد از مدتی گم می‌شوند! در عوض آن‌ها به رمز رشد درختان این جنگل پی برده‌اند، الگوریتم ساخت یک درخت $n$ رأسی در جنگل تصادفی به این صورت است:

ابتدا راس $1$ به عنوان ریشه قرار می‌گیرد، سپس در $n - 1$ لحظه بعد، در لحظه $i$ ام، پدر راس $i + 1$ به طور تصادفی با شانس برابر بین رئوس $1$ تا $i$ انتخاب می شود و راس $i + 1$ به درخت اضافه می‌شود.

امیر حین تلاش آن‌ها برای خروج از جنگل نقشه‌ای قدیمی پیدا می‌کند که به زبانی باستانی نوشته شده است. امیر شروع به رمزگشایی این زبان می‌کند و می‌فهمد که زیبایی یک درخت از دید یونانیان باستان برابر تعداد دوتایی‌های $(u,v)$ از راس های درخت است که ارتفاع برابر دارند و $u < v$ است. او بدون دانستن امید ریاضی زیبایی یک درخت $n$ راسی در جنگل تصادفی نمی‌تواند بخش دوم نقشه را رمزگشایی کند!

تا وقتی که امیر مشغول رمزگشایی دیگر بخش‌های نقشه است، به مهدی کمک کنید جواب مسأله را به پیمانهٔ $M$ بدست آورد و به امیر بدهد تا آن‌ها را از جنگل تصادفی نجات بدهد!

امید ریاضی خواسته شده را می‌توان به صورت $\frac P Q$ که $P$ و $Q$ نسبت به هم اولند. در این صورت $P.Q^{-1}$ را به پیمانه $M$ محاسبه کنید.

ورودی🔗

تنها سطر ورودی شامل عدد طبیعی $n$، تعداد رئوس درخت، و عدد اول $M$ است.

$1 \leq n \leq 5000$ $10^8 \leq M \leq 10^9$

خروجی🔗

در تنها سطر خروجی، امید ریاضی تعداد جفت راس های هم‌طبقه در یک درخت $n$ راسی تصادفی را به پیمانه $M$ چاپ کنید.

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

مثال‌ها🔗

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

4 100000007

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

16666669

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

6 998244353

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

16637409 

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

10 349101829

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

213807563

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

100 998244853

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

439156355

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

چنگیزخان با ارتش عظیمش بار دیگر در فکر حمله به چین است و در پی این تصمیم به سربازانش دستور داده است که $n$ نردبان با $h$ پله پای دیوار بزرگ چین بگذارند. می‌دانیم سربازان چنگیز اگر روی نردبانی باشند هر ثانیه دقیقاً ۱ پله بالا می‌روند. همچنین هر ثانیه یکی از دو اتفاق زیر رخ می‌دهد:

• چنگیز به سربازانش دستور می‌دهد که به ازای نردبان‌های $l$ ام تا $r$ ام از هر نردبان دقیقاً $x$ نفر همزمان شروع به بالا رفتن بکنند.
• اینکه سربازان چینی از بالای دیوار سنگی بر روی نردبان $i$ ام می‌اندازند که $k$ نفر بالایی نردبان را می‌کشد. دقت کنید که اگر کمتر از $k$ نفر روی نردبان باشند، سنگ تمام افراد روی نردبان را می‌کشد و سپس بدون آسیب دیگری به زمین می‌رسد.

این حمله برای $q$ ثانیه اتفاق جدید دارد. بعد از آن هم چنگیز صدایش می‌گیرد و دستور دیگری نمی‌دهد. البته سربازان چینی نیز دیگر سنگی ندارند. سربازان مغولی که روی نردبان‌ها هستند از ترس چنگیز همچنان به بالا رفتن ادامه می‌دهند. برای درک بیشتر سوال به مثال‌ها توجه کنید.

در پایان، چنگیز که از حساب و کتاب بدش می‌آید، از شما می‌خواهد به او کمک کنید که بداند چند تن از سربازانش به بالای نردبان‌ها رسیده‌اند.

ورودی🔗

در خط اول به ترتیب $n$ و $q$ و $h$ می آیند که نشان دهنده تعداد نردبان‌ها، تعداد اتفاقات و تعداد پله‌های نردبان‌ها هستند.

$1 \leq n, q \leq 200\,000, \quad 1 \leq h \leq 10^9$

در ادامه $q$ خط داده می شوند که هر یک یکی از دو حالت زیر را دارند که نشان دهنده اتفاق نوع اول و دوم هستند.

• $1 \; l\;r\;x$
• $2\;i\;k$

$1 \leq l \leq r \leq n , \quad 1 \leq x \leq 10^7$ $1 \leq i \leq n , \quad 1 \leq k \leq 10^7$

خروجی🔗

در تنها خط خروجی بگویید که چند سرباز چنگیز بعد از $10^{18}$ ثانیه به بالای نردبان‌ها می‌رسند.

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

مثال‌ها🔗

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

3 3 1
1 1 2 1
2 1 1
2 2 1

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

1

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

5 6 3
2 4 5
1 1 5 2
1 1 3 1
2 4 3
1 1 1 9
2 5 2

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

20