====== نخود (Nokhod) ======


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

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


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


===== ورودی =====


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

به ازای هر سناریو، در خط اول تعداد راس‌های درخت $n$ می‌آید. 

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

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

===== خروجی =====

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



===== زیرمسئله‌ها =====
  * زیرمسئله اول (۲۱ نمره): $b_i \neq -1$
  * زیرمسئله دوم (۲۷ نمره): راس ۱ به همه راس‌ها مسیر دارد.
  * زیرمسئله سوم (۵۲ نمره): بدون محدودیت اضافی


===== محدودیت‌ها =====
  * $1 \leq n, T \leq 2 \times 10^5$
  * $1 \leq v, u \leq n$
  * $-1 \leq b_i \leq 10^{12}$
  * تضمین می‌شود یال‌های ورودی تشکیل درخت می‌دهند.
  * تضمین می‌شود جمع $n$ ها به ازای تمام سناریو ها از $2 \times 10^5$ بیشتر نمی‌شود. 



===== ورودی و خروجی نمونه =====

<WRAP :en>
^  ورودی نمونه  ^  خروجی نمونه  ^
| <code>
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
</code> | <code>
NO
NO
YES
</code> |
</WRAP>

<span hi>
سعی کنید سوالات را با کمترین راهنمایی از بالا به پایین حل کنید.
</span>

<راهنمایی>
فرض کنید درخت را از راس ۱ ریشه دار کنیم. در این صورت به ازای هر راس $v \neq 1$ که $v$ به $par[v]$ یال جهت‌دار داشته باشد نخودی به زیردرخت $v$ وارد نمی شود و اگر جهت یال از $par[v]$ به $v$ باشد نخودی از زیردرخت $v$ خارج نمی شود.
</راهنمایی>


<راهنمایی>
فرض کنید $sum_a[v]$ مجموع $a[i]$ها به ازای $i$ هایی که در زیردرخت $v$ هستند باشد و به طور مشابه $sum_b[v]$ مجموع $b[i]$ ها به ازای $i$ هایی که در زیر درخت $v$ هستند باشد. آن گاه برای حالت $b[i] \neq 1$ اگر سه شرط زیر برقرار باشد جواب $yes$ و در غیر این صورت جواب $no$ خواهد بود.

شرط ۱: به ازای $v \neq 1$ که $v$ به $par[v]$ یال جهت دار داشته باشد $sum_b[v] \le sum_a[v]$
شرط 2: به ازای $v \neq 1$ که $par[v]$ به $v$ یال جهت دار داشته باشد $sum_a[v] \le sum_b[v]$
شرط 3: $sum_a[v] = sum_b[v]$
</راهنمایی>

<راهنمایی>
برای حالت کلی سوال اگر بتوانیم $b[i]=-1$ را طوری مقدار دهی کنیم که شروط راهنمایی ۲ برقرار باشد پاسخ $yes$  و در غیر این صورت پاسخ $no$ خواهد بود.
</راهنمایی>

<راهنمایی>
قصد داریم برای هر $v$ مقادیر مختلف $x$ رو حساب کنیم به طوری که بتوانیم $b[i]=-1$ ها در زیردرخت $v$ رو طوری مقدار دهی کنیم که شروط راهنمایی ۲ برای رئوس زیردرخت $v$ برقرار باشد و $sum_b[v]=x$ باشد. برای پاسخ سوال کافیست بررسی کنیم که آیا $sum_a[1]$ جزو مقادیر راس ۱ می‌باشد یا خیر.
</راهنمایی>

<راهنمایی>
مقادیر حساب شده در راهنمایی ۴ برای هر راس بازه‌ای متوالی از اعداد هستند.
</راهنمایی>

<راهنمایی>
به برنامه‌نویسی پویا فکر کنید.
</راهنمایی>

<راهنمایی>
مقدار $dp[v]$ را برابر با بازه مجموعه اعداد گفته شده در راهنمایی ۴ برای راس $v$ قرار می دهیم. آنگاه می توان $dp[v]$ را با کمک $dp$ قرزندان $v$ محسابه کرد.
</راهنمایی>

  * [[سوال ۲|سوال بعد]]