D. Мисс Punyverse
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дуб имеет $$$n$$$ гнезд, пронумерованных целыми числами от $$$1$$$ до $$$n$$$. Гнездо $$$i$$$ это дом для $$$b_i$$$ пчел и $$$w_i$$$ ос.

Некоторые гнезда соединены ветками. Мы называем два гнезда соседними если существует ветка, соединяющая их. Простой путь из гнезда $$$x$$$ в $$$y$$$ задается последовательностью $$$s_0, \ldots, s_p$$$ различных гнезд, где $$$p$$$ это неотрицательное целое число и $$$s_0 = x$$$, $$$s_p = y$$$ и $$$s_{i-1}$$$ и $$$s_{i}$$$ соседние для всех $$$i = 1, \ldots, p$$$. Ветки дуба расположены так, что для любой пары гнезд $$$x$$$ и $$$y$$$ существует единственный простой путь из $$$x$$$ в $$$y$$$. По причине этого и биологи и программисты согласны, что дуб, по факту, является деревом.

Деревня это непустое множество $$$V$$$ гнезд, такое что для всех $$$x$$$ и $$$y$$$ из $$$V$$$, существует простой путь из $$$x$$$ в $$$y$$$, все гнезда вдоль которого также лежат в $$$V$$$.

Множество деревень $$$\cal P$$$ называется разбиением если каждое из $$$n$$$ гнезд содержится в ровно одной деревне из $$$\cal P$$$. Другими словами, никакие две деревни из $$$\cal P$$$ не содержат одно и то же гнездо и в объединении дают все $$$n$$$ гнезд.

На дубе проводится ежегодный конкурс красоты мисс Punyverse. Всего два участника участвуют в этом году, это некрасивая оса и красивая пчела. Победитель конкурса красоты определяется голосованием, систему которого мы сейчас опишем. Пусть $$$\mathcal{P}$$$ это разбиение гнезд на $$$m$$$ деревень $$$V_1, \ldots, V_m$$$. Проводится локальные выборы в каждой деревне. Каждое насекомое в деревне голосует за свое любимое насекомое. Если в деревне окажется, что строго больше голосов отдано за некрасивую осу чем за красивую пчелу, тогда некрасивая оса объявляется победителем в этой деревне. Иначе, красивая пчела побеждает.

Известно, что пчелы всегда голосуют за пчел, то есть проголосуют за красивую пчелу в этом году и осы всегда голосуют за ос, то есть проголосуют за некрасивую осу в этом году. Все насекомые в улье участвуют в голосовании.

Мэр Waspacito, а также его заместитель Alexwasp, хотят, чтобы некрасивая оса победила. Они имеют влияние и могут выбрать разбиение дуба на ровно $$$m$$$ деревень. Если они выберут разбиение оптимально, определите максимальное количество деревень, в которых победит некрасивая оса.

Входные данные

В первой строке находится единственное целое число $$$t$$$ ($$$1 \le t \le 100$$$), количество тестовых случаев. В следующих строках находится описание тестовых случаев.

В первой строке каждого тестового случая находится два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le m \le n \le 3000$$$). Во второй строке находится $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$0 \le b_i \le 10^9$$$). В третьей строке находится $$$n$$$ целых чисел $$$w_1, w_2, \ldots, w_n$$$ ($$$0 \le w_i \le 10^9$$$). В следующих $$$n - 1$$$ находятся описания соседних пар гнезд, $$$i$$$-я из них содержит два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$, $$$x_i \neq y_i$$$), обозначающих номера гнезд, соединенных веткой. Гарантируется, что эти пары задают дерево.

Гарантируется, что сумма $$$n$$$ по всем тестовым случаям не превосходит $$$10^5$$$.

Выходные данные

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

Пример
Входные данные
2
4 3
10 160 70 50
70 111 111 0
1 2
2 3
3 4
2 1
143 420
214 349
2 1
Выходные данные
2
0
Примечание

В первом тестовом случае, нужно разделить $$$n = 4$$$ гнезд на $$$m = 3$$$ деревень. Мы можем так разделить, что некрасивая оса победит в $$$2$$$ деревнях, например с помощью такого разбиения: $$$\{\{1, 2\}, \{3\}, \{4\}\}$$$. В этом разбиении:

  • Некрасивая оса побеждает в деревне $$$\{1, 2\}$$$, получив $$$181$$$ голосов тогда как красивая пчела получила $$$170$$$ голосов;
  • Некрасивая оса также побеждает в деревне $$$\{3\}$$$, получив $$$111$$$ голосов тогда как красивая пчела получила $$$70$$$ голосов;
  • Некрасивая оса проиграет в деревне $$$\{4\}$$$, получив $$$0$$$ голосов тогда как красивая пчела получила $$$50$$$.

Таким образом некрасивая оса победила в $$$2$$$ деревнях и можно показать, что это максимально возможное число.

Во втором тесте мы должны разделить $$$n = 2$$$ гнезд на $$$m = 1$$$ деревень. Есть только один способ это сделать: $$$\{\{1, 2\}\}$$$. В этом разбиении некрасивая оса получит $$$563$$$ голосов и красивая пчела также получит $$$563$$$ голосов. Некрасивая оса побеждает, если получает строго больше голосов. Поэтому некрасивая оса не выиграет ни в какой деревне.