CF1280D.Miss Punyverse

The Oak has $n$ nesting places, numbered with integers from $1$ to $n$. Nesting place $i$ is home to $b_i$ bees and $w_i$ wasps.

Some nesting places are connected by branches. We call two nesting places adjacent if there exists a branch between them. A simple path from nesting place $x$ to $y$ is given by a sequence $s_0, \ldots, s_p$ of distinct nesting places, where $p$ is a non-negative integer, $s_0 = x$, $s_p = y$, and $s_{i-1}$ and $s_{i}$ are adjacent for each $i = 1, \ldots, p$. The branches of The Oak are set up in such a way that for any two pairs of nesting places $x$ and $y$, there exists a unique simple path from $x$ to $y$. Because of this, biologists and computer scientists agree that The Oak is in fact, a tree.

A village is a nonempty set $V$ of nesting places such that for any two $x$ and $y$ in $V$, there exists a simple path from $x$ to $y$ whose intermediate nesting places all lie in $V$.

A set of villages $\cal P$ is called a partition if each of the $n$ nesting places is contained in exactly one of the villages in $\cal P$. In other words, no two villages in $\cal P$ share any common nesting place, and altogether, they contain all $n$ nesting places.

The Oak holds its annual Miss Punyverse beauty pageant. The two contestants this year are Ugly Wasp and Pretty Bee. The winner of the beauty pageant is determined by voting, which we will now explain. Suppose $\mathcal{P}$ is a partition of the nesting places into $m$ villages $V_1, \ldots, V_m$. There is a local election in each village. Each of the insects in this village vote for their favorite contestant. If there are strictly more votes for Ugly Wasp than Pretty Bee, then Ugly Wasp is said to win in that village. Otherwise, Pretty Bee wins. Whoever wins in the most number of villages wins.

As it always goes with these pageants, bees always vote for the bee (which is Pretty Bee this year) and wasps always vote for the wasp (which is Ugly Wasp this year). Unlike their general elections, no one abstains from voting for Miss Punyverse as everyone takes it very seriously.

Mayor Waspacito, and his assistant Alexwasp, wants Ugly Wasp to win. He has the power to choose how to partition The Oak into exactly $m$ villages. If he chooses the partition optimally, determine the maximum number of villages in which Ugly Wasp wins.

橡树有 $n$ 个巢穴，编号为 $1$ 至 $n$ 的整数。巢穴 $i$ 中居住着 $b_i$ 只蜜蜂和 $w_i$ 只黄蜂。

部分巢穴之间由枝条连接。若两个巢穴之间存在一条枝条，则称它们相邻。从巢穴 $x$ 到 $y$ 的一条简单路径定义为一个由互不相同的巢穴构成的序列 $s_0, \ldots, s_p$，其中 $p$ 是一个非负整数，满足 $s_0 = x$、$s_p = y$，且对每个 $i = 1, \ldots, p$，$s_{i-1}$ 与 $s_i$ 相邻。橡树的枝条结构满足如下性质：对任意两个巢穴 $x$ 和 $y$，均存在唯一一条从 $x$ 到 $y$ 的简单路径。正因如此，生物学家与计算机科学家一致认为，橡树实际上是一棵树。

一个村落（village）是指一个非空的巢穴集合 $V$，使得对任意 $x, y \in V$，均存在一条从 $x$ 到 $y$ 的简单路径，且该路径上所有中间巢穴（即除端点外的所有巢穴）均属于 $V$。

一个村落集合 $\cal P$ 称为一个划分（partition），当且仅当全部 $n$ 个巢穴恰好属于 $\cal P$ 中的一个村落。换言之，$\cal P$ 中任意两个村落互不相交，且它们的并集恰好包含全部 $n$ 个巢穴。

橡树每年举办“微宇宙小姐”（Miss Punyverse）选美大赛。今年的两位参赛者是“丑陋黄蜂”（Ugly Wasp）与“漂亮蜜蜂”（Pretty Bee）。大赛获胜者通过投票决定，规则如下：设 $\mathcal{P}$ 是将全部巢穴划分为 $m$ 个村落 $V_1, \ldots, V_m$ 的一个划分。每个村落内举行一次地方选举，该村落内的所有昆虫为其最喜爱的参赛者投票。若“丑陋黄蜂”的得票数严格多于“漂亮蜜蜂”，则称“丑陋黄蜂”在该村落中获胜；否则，“漂亮蜜蜂”获胜。最终，在最多数量的村落中获胜者即为大赛总冠军。

正如往届大赛一样，蜜蜂总是投票给蜜蜂（即今年的“漂亮蜜蜂”），而黄蜂总是投票给黄蜂（即今年的“丑陋黄蜂”）。与常规大选不同的是，在“微宇宙小姐”大赛中，没有任何昆虫弃权——因为每个人都对此极为重视。

黄蜂市长瓦斯帕西托（Waspacito）及其助理亚历克斯黄蜂（Alexwasp）希望“丑陋黄蜂”获胜。他有权自主决定如何将橡树恰好划分为 $m$ 个村落。若他选择最优的划分方式，请确定“丑陋黄蜂”最多能在多少个村落中获胜。

The first line of input contains a single integer $t$ ($1 \le t \le 100$) denoting the number of test cases. The next lines contain descriptions of the test cases.

The first line of each test case contains two space-separated integers $n$ and $m$ ($1 \le m \le n \le 3000$). The second line contains $n$ space-separated integers $b_1, b_2, \ldots, b_n$ ($0 \le b_i \le 10^9$). The third line contains $n$ space-separated integers $w_1, w_2, \ldots, w_n$ ($0 \le w_i \le 10^9$). The next $n - 1$ lines describe the pairs of adjacent nesting places. In particular, the $i$-th of them contains two space-separated integers $x_i$ and $y_i$ ($1 \le x_i, y_i \le n$, $x_i \neq y_i$) denoting the numbers of two adjacent nesting places. It is guaranteed that these pairs form a tree.

It is guaranteed that the sum of $n$ in a single file is at most $10^5$.

输入的第一行包含一个整数 $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$。

For each test case, output a single line containing a single integer denoting the maximum number of villages in which Ugly Wasp wins, among all partitions of The Oak into $m$ villages.

对于每个测试用例，输出一行，包含一个整数，表示在将橡树村划分为 $m$ 个村庄的所有划分方案中，丑蜂获胜的村庄数量的最大值。

In the first test case, we need to partition the $n = 4$ nesting places into $m = 3$ villages. We can make Ugly Wasp win in $2$ villages via the following partition: ${{1, 2}, {3}, {4}}$. In this partition,

• Ugly Wasp wins in village ${1, 2}$, garnering $181$ votes as opposed to Pretty Bee's $170$;
• Ugly Wasp also wins in village ${3}$, garnering $111$ votes as opposed to Pretty Bee's $70$;
• Ugly Wasp loses in the village ${4}$, garnering $0$ votes as opposed to Pretty Bee's $50$.

Thus, Ugly Wasp wins in $2$ villages, and it can be shown that this is the maximum possible number.

In the second test case, we need to partition the $n = 2$ nesting places into $m = 1$ village. There is only one way to do this: ${{1, 2}}$. In this partition's sole village, Ugly Wasp gets $563$ votes, and Pretty Bee also gets $563$ votes. Ugly Wasp needs strictly more votes in order to win. Therefore, Ugly Wasp doesn't win in any village.

在第一个测试用例中，我们需要将 $n = 4$ 个巢穴划分为 $m = 3$ 个村庄。我们可以通过如下划分使丑蜂（Ugly Wasp）在 $2$ 个村庄中获胜：$\{\{1, 2\}, \{3\}, \{4\}\}$。在此划分下：

• 丑蜂在村庄 $\{1, 2\}$ 中获胜，获得 $181$ 票，而美蜂（Pretty Bee）获得 $170$ 票；
• 丑蜂在村庄 $\{3\}$ 中也获胜，获得 $111$ 票，而美蜂获得 $70$ 票；
• 丑蜂在村庄 $\{4\}$ 中落败，获得 $0$ 票，而美蜂获得 $50$ 票。

因此，丑蜂在 $2$ 个村庄中获胜，且可以证明这是可能达到的最大值。

在第二个测试用例中，我们需要将 $n = 2$ 个巢穴划分为 $m = 1$ 个村庄。仅存在一种划分方式：$\{\{1, 2\}\}$。在此划分的唯一村庄中，丑蜂获得 $563$ 票，美蜂也获得 $563$ 票。丑蜂需获得严格更多的票数才能获胜。因此，丑蜂在任何村庄中均未获胜。