博格丹叔叔在弗林特船长的船员中呆了很长时间,有时会怀念他的祖国。今天他告诉你他的国家是如何引入幸福指数的。
有 $$$n$$$ 个城市和连接成对城市的 $$$n−1$$$ 无向道路。任何城市的公民都可以通过这些道路到达任何其他城市。城市编号从 $$$1$$$ 到 $$$n$$$,城市 $$$1$$$ 是首都。换句话说,这个国家是树形结构。
有 $$$m$$$ 公民居住在该国。 $$$p_i$$$ 人居住在第 $$$i$$$ 个城市,但他们都在首都工作。晚上,所有公民都使用最短路线返回自己的家乡。
每个人都有自己的心情:有人离开工作场所心情很好,但有人已经心情不好。而且任何人都可能在回家乡的路上破坏自己的心情。如果一个人心情不好,他就不会改善它。
每个城市都安装了幸福感探测器,监测每个到访该城市的人的幸福感。第 $$$i$$$ 个城市的检测器计算幸福指数 $$$h_i$$$,即心情好的人数减去心情不好的人数。简单地说,一个人的情绪在城市里不会改变。
幸福感检测器仍在开发中,因此判断一个人的幸福感有可能会出现错误。一天傍晚,当所有公民顺利回家时,政府请博格丹叔叔(全国最好的程序员)检查收集的幸福指数的正确性。
博格丹叔叔成功解决了这个问题。你能做同样的事吗?
更正式地说,您需要检查:“是否有可能,在所有人都回家后,对于每个城市$$$i$$$,幸福指数将恰好等于$$$h_i$$$”。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10000$$$) — 测试用例的数量。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 10^5$$$; $$$0 \le m \le 10^9$$$) - 城市和公民的数量。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$p_1, p_2, \ldots, p_{n}$$$ ($$$0 \le p_i \le m$$$; $$$p_1 + p_2 + \ldots + p_{n} = m$$$),其中 $$$p_i$$$ 是居住在第 $$$i$$$ 个城市。
第三行包含$$$n$$$整数$$$h_1, h_2, \ldots, h_{n}$$$ ($$$-10^9 \le h_i \le 10^9$$$),其中$$$h_i$$$是计算出的第$$$i$$$个城市的幸福指数。
接下来的 $$$n − 1$$$ 行包含道路描述,每行一个。每行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$; $$$x_i \neq y_i$$$),其中 $$$x_i$$$ 和 $$$y_i$$$ 是由第 $$$i$$$ 条道路连接的城市。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,如果收集的数据正确,则打印 YES,否则打印 NO。在任何情况下都可以打印 YES 或 NO 字符。
示例
输入 #1
2 7 4 1 0 1 1 0 1 0 4 0 0 -1 0 -1 0 1 2 1 3 1 4 3 5 3 6 3 7 5 11 1 2 5 2 1 -11 -2 -6 -2 -1 1 2 1 3 1 4 3 5
输出 #1
YES YES
输入 #2
2 4 4 1 1 1 1 4 1 -3 -1 1 2 1 3 1 4 3 13 3 3 7 13 1 4 1 2 1 3
输出 #2
NO NO
注意
让我们看一下第一个样本的第一个测试用例:
起初,所有公民都在首都。让我们描述一种可能的情况:
- 城市人$$$1$$$:住在首都,心情很好;
- 来自城市$$$4$$$的人:他访问了城市$$$1$$$和$$$4$$$,他的心情在城市$$$1$$$和$$$4$$$之间被破坏了;
- 来自城市$$$3$$$的人:他心情不错地访问了城市$$$1$$$和$$$3$$$;
- 来自城市$$$6$$$的人:他访问了城市$$$1$$$、$$$3$$$和$$$6$$$,他的心情在城市$$$1$$$和$$$3$$$之间被破坏了;
- $$$h_1 = 4 - 0 = 4$$$,
- $$$h_2 = 0$$$,
- $$$h_3 = 1 - 1 = 0$$$,
- $$$h_4 = 0 - 1 = -1$$$,
- $$$h_5 = 0$$$,
- $$$h_6 = 0 - 1 = -1$$$,
- $$$h_7 = 0$$$。
第一个测试的第二种情况:
首都的所有人都开始心情不好了——这是唯一可能的情况。
第二次测试的第一种情况:
第二次测试的第二种情况:
可以证明,在第二次测试的两种情况下都没有办法达到给定的幸福指数。