← 返回题目列表

Codeforces · 1388/C

C. 博格丹叔叔和乡村幸福

中文机器翻译题面 查看原题

博格丹叔叔在弗林特船长的船员中呆了很长时间,有时会怀念他的祖国。今天他告诉你他的国家是如何引入幸福指数的。

有 $$$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$$$。

第一个测试的第二种情况:

首都的所有人都开始心情不好了——这是唯一可能的情况。

第二次测试的第一种情况:

第二次测试的第二种情况:

可以证明,在第二次测试的两种情况下都没有办法达到给定的幸福指数。