橡树有 $$$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}$$$ 和对于每个 $$$i = 1, \ldots, p$$$,$$$s_{i}$$$ 是相邻的。橡树的分支是这样设置的,对于任意两对筑巢地点 $$$x$$$ 和 $$$y$$$,都存在一条从 $$$x$$$ 到 $$$y$$$ 的唯一简单路径。正因为如此,生物学家和计算机科学家一致认为橡树实际上是一棵树。
村庄是嵌套位置的非空集合$$$V$$$,因此对于$$$V$$$中的任意两个$$$x$$$和$$$y$$$,存在一条从$$$x$$$到$$$y$$$的简单路径,其中间嵌套位置都位于$$$V$$$。
如果 $$$n$$$ 中的每个嵌套位置恰好包含在 $$$\cal P$$$ 中的一个村庄中,则一组村庄 $$$\cal P$$$ 称为分区。换句话说,$$$\cal P$$$ 中没有两个村庄共享任何共同的筑巢地点,并且它们总共包含所有 $$$n$$$ 筑巢地点。
The Oak 举办一年一度的 Miss Punyverse 选美比赛。今年的两位参赛者是丑黄蜂和漂亮蜜蜂。选美比赛的获胜者是通过投票决定的,我们现在对此进行解释。假设 $$$\mathcal{P}$$$ 是将筑巢地点划分为 $$$m$$$ 个村庄 $$$V_1, \ldots, V_m$$$。每个村都有地方选举。这个村子里的每只昆虫都投票选出他们最喜欢的参赛者。如果“丑黄蜂”的票数严格多于“漂亮蜜蜂”的票数,则据说“丑黄蜂”在该村庄获胜。否则,漂亮蜜蜂获胜。谁赢得的村庄数量最多,谁就获胜。
与这些选美比赛一样,蜜蜂总是投票给蜜蜂(今年是漂亮蜜蜂),而黄蜂总是投票给黄蜂(今年是丑陋黄蜂)。与他们的大选不同,没有人放弃投票给 Punyverse 小姐,因为每个人都非常认真地对待它。
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$$$。
输出
对于每个测试用例,输出一行,其中包含一个整数,表示在 The Oak 的所有分区中 Ugly Wasp 获胜的村庄的最大数量为 $$$m$$$ 村庄。
示例
输入 #1
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
输出 #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$$$ 选票。丑陋的黄蜂需要更多的选票才能获胜。因此,丑黄蜂在任何村庄都没有获胜。