- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
- آزمون عملی اول فاینال سی و سومین دوره المپیاد کامپیوتر ایران
کیومرث یک درخت \(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 را چاپ کنید.
زیرمسئلهها
| زیرمسئله | نمره | محدودیت |
|---|---|---|
| ۱ | ۲۱ | \(b_i \neq -1\) |
| ۲ | ۲۷ | راس ۱ به همه راسها مسیر دارد. |
| ۳ | ۵۲ | بدون محدودیت اضافی |
مثالها
ورودی نمونه ۱
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