C. Дядя Богдан и настроение страны
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дядя Богдан, будучи матросом на корабле капитана Флинта, порой скучает по родине. Сегодня он рассказал о том, как в его государстве вводили индекс счастья населения.

Всего в стране $$$n$$$ городов и $$$n−1$$$ двусторонняя дорога, соединяющая некоторые пары городов. Из любого города можно попасть в любой другой, пройдя по некоторым дорогам. Города пронумерованы от $$$1$$$ до $$$n$$$ и город $$$1$$$ является столицей. Таким образом, структура государства является корневым деревом.

Всего в стране проживает $$$m$$$ человек. В $$$i$$$-м городе проживает $$$p_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 можно выводить в любом регистре.

Примеры
Входные данные
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
Выходные данные
YES
YES
Входные данные
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
Выходные данные
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$$$.

Второй набор первого теста:

У всех жителей страны уже испортилось настроение в столице. Это единственный возможный вариант развития событий.

Первый набор второго теста:

Второй набор второго теста:

Можно показать, что требуемые значения индексов счастья недостижимы в обоих наборах второго теста.