T514967 「KDOI-10」Water

[Chinese Statement](https://www.luogu.com.cn/problem/T510354?contestId=200849). You must submit your code at the Chinese version of the statement. |Input|Output|Time Limit|Memory Limit| |:--:|:--:|:--:|:--:| |standard input|standard output|2.0 s|512 MiB| This problem has $25$ tests. The full score is $100$ points, and $4$ points per test.

Little S has a tree with $n$ vertices, rooted at vertex $1$. On vertex $i$ $(1\le i\le n)$, there is a water cup with an initial temperature of $a_i$. Little S, who picked up a water cup and drank water without knowing the temperature and was scalded many times, decided to change all the temperatures of the water in the cups to $0$. Now, Little S can do the following two types of operations an arbitrary number of times (possibly zero): - Use a heater at vertex $i$. This will make the temperature of the water cups on all vertices in subtree $i$ increase by $1$; - Or, blow a gust of wind from a **leaf** $i$. This will make the temperature of the water cups on the route between $1$ and $i$ decrease by $1$. Help Little S determine whether he can make the temperature of all the water cups become $0$.

无

无

**Sample 1 Explanation** Let $A_u$ be a heating operation on vertex $u$, $B_u$ be a wind operation from vertex $u$ and $(S)^k$ be repeating the operations in $S$ for $k$ times. - In the first, third and fourth test case, it can be proven that Little S can't make the temperature of all the water cups $0$; - In the second test case, a possible operation sequence is $B_3(A_4)^3(B_4)^5B_5$; - For the fifth test case, a possible operation sequence is $(A_4)^3A_1$. **Sample 2** See `water/water2.in` and `water/water2.ans` in the attachments. This sample satisfies the constraints of test $3$. **Sample 3** See `water/water3.in` and `water/water3.ans` in the attachments. This sample satisfies the constraints of test $7,8$. **Sample 4** See `water/water4.in` and `water/water4.ans` in the attachments. This sample satisfies the constraints of test $12$. **Sample 5** See `water/water5.in` and `water/water5.ans` in the attachments. This sample satisfies the constraints of test $13,14$. **Sample 6** See `water/water6.in` and `water/water6.ans` in the attachments. This sample satisfies the constraints of test $15\sim 17$. **Sample 7** See `water/water7.in` and `water/water7.ans` in the attachments. This sample satisfies the constraints of test $18\sim 21$. *** **Constraints** Let $\sum n$ be the sum of $n$ over all test cases in a single test. For all the tests, it is guaranteed that: - $1\leq t\leq 1\,000$; - $2\leq n\leq 10^5$, $\sum n\le 10^6$; - For each $2\le i\le n$, $1\le f_i