P11189 「KDOI-10」水杯降温

[English Statement](https://www.luogu.com.cn/problem/T514967). You must submit your code at the Chinese version of the statement. **本场比赛所有题目从标准输入读入数据，输出到标准输出。**

小 S 有一棵包含 $n$ 个节点的有根树，且根为节点 $1$。节点 $i$ $(1\le i\le n)$ 上放置了一个初始水温为 $a_i$ 的水杯。 在不知道水温的情况下拿起水杯喝水并被烫了 inf 次的小 S 决定将这些水杯的水温全部变为 $0$ 后再喝它们。 现在，小 S 可以分别进行以下两种操作任意次： * 使用一个在节点 $i$ 的加热装置。这会使以 $i$ 为根的子树内所有水杯里的水温均增加 $1$； * 或者，从某个**叶子**节点 $i$ 向根方向吹一阵风。这会使 $i$ 到根所有水杯里的水温均减少 $1$。 请你帮小 S 判断：能否将所有节点上的水杯的水温都变为 $0$。

无

无

**【样例 1 解释】** 记 $A_u$ 表示在节点 $u$ 使用加热装置的操作，$B_u$ 表示从节点 $u$ 吹一阵风的操作，$(S)^k$ 表示将操作序列 $S$ 重复 $k$ 次。 - 对于第一、三、四组测试数据，可以证明，小 S 无法将所有水杯的水温都变为 $0$； - 对于第二组测试数据，一种可能的操作序列为：$B_3(A_4)^2(B_4)^4B_5$； - 对于第五组测试数据，一种可能的操作序列为：$(A_4)^3A_1$。 **【样例 2】** 见选手目录下的 `water/water2.in` 与 `water/water2.ans`。 这个样例满足测试点 $3$ 的约束条件。 **【样例 3】** 见选手目录下的 `water/water3.in` 与 `water/water3.ans`。 这个样例满足测试点 $7,8$ 的约束条件。 **【样例 4】** 见选手目录下的 `water/water4.in` 与 `water/water4.ans`。 这个样例满足测试点 $12$ 的约束条件。 **【样例 5】** 见选手目录下的 `water/water5.in` 与 `water/water5.ans`。 这个样例满足测试点 $13,14$ 的约束条件。 **【样例 6】** 见选手目录下的 `water/water6.in` 与 `water/water6.ans`。 这个样例满足测试点 $15\sim 17$ 的约束条件。 **【样例 7】** 见选手目录下的 `water/water7.in` 与 `water/water7.ans`。 这个样例满足测试点 $18\sim 21$ 的约束条件。 *** **【数据范围】** 记 $\sum n$ 为单个测试点内所有测试数据中 $n$ 的和。 对于全部的测试数据，保证： - $1\leq t\leq 1\,000$； - $2\leq n\leq 10^5$，$\sum n\le 10^6$； - 对于任意 $2\le i\le n$，$1\le f_i