CF1280D Miss Punyverse

橡树上有 $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$，都存在唯一的一条简单路径连接它们。因此，生物学家和计算机科学家一致认为橡树的结构实际上是一棵树。 一个“村庄”是指一个非空的巢穴集合 $V$，满足对于 $V$ 中任意两个 $x$ 和 $y$，存在一条简单路径从 $x$ 到 $y$，且路径上的中间巢穴都属于 $V$。 一组村庄集合 $\cal P$ 被称为一个划分，如果每个巢穴恰好属于 $\cal P$ 中的一个村庄。换句话说，$\cal P$ 中任意两个村庄没有公共巢穴，并且所有 $n$ 个巢穴都被包含在这些村庄中。 橡树每年都会举办 Miss Punyverse 选美大赛。今年的两位参赛者分别是 Ugly Wasp 和 Pretty Bee。选美大赛的获胜者由投票决定，具体规则如下：假设将所有巢穴划分为 $m$ 个村庄 $V_1, \ldots, V_m$，每个村庄举行一次本地选举。村庄中的每只昆虫都会为自己喜欢的选手投票。如果 Ugly Wasp 的得票数严格多于 Pretty Bee，则 Ugly Wasp 赢得该村庄，否则 Pretty Bee 获胜。最终，在最多村庄获胜的选手成为总冠军。 和往常一样，蜜蜂都投给蜜蜂（即 Pretty Bee），黄蜂都投给黄蜂（即 Ugly Wasp）。与一般选举不同，没有昆虫会弃权，每个人都非常重视 Miss Punyverse。 市长 Waspacito 和他的助手 Alexwasp 希望 Ugly Wasp 获胜。他有权决定如何将橡树划分为恰好 $m$ 个村庄。请你帮他计算，在最优划分下，Ugly Wasp 最多能在多少个村庄获胜。

输入的第一行为一个整数 $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$ 行，每行两个整数 $x_i$ 和 $y_i$（$1 \le x_i, y_i \le n$，$x_i \neq y_i$），表示一对相邻的巢穴。保证这些边构成一棵树。 保证单个文件中所有 $n$ 的总和不超过 $10^5$。

对于每个测试用例，输出一行一个整数，表示在将橡树划分为 $m$ 个村庄的所有方案中，Ugly Wasp 最多能在多少个村庄获胜。

在第一个测试用例中，需要将 $n=4$ 个巢穴划分为 $m=3$ 个村庄。可以通过如下划分让 Ugly Wasp 在 $2$ 个村庄获胜：$\{\{1, 2\}, \{3\}, \{4\}\}$。在该划分下： - Ugly Wasp 在村庄 $\{1, 2\}$ 获胜，获得 $181$ 票，而 Pretty Bee 获得 $170$ 票； - Ugly Wasp 也在村庄 $\{3\}$ 获胜，获得 $111$ 票，而 Pretty Bee 获得 $70$ 票； - Ugly Wasp 在村庄 $\{4\}$ 失败，获得 $0$ 票，而 Pretty Bee 获得 $50$ 票。 因此 Ugly Wasp 在 $2$ 个村庄获胜，并且可以证明这是最大可能值。 在第二个测试用例中，需要将 $n=2$ 个巢穴划分为 $m=1$ 个村庄。只有一种划分方式：$\{\{1, 2\}\}$。在这个唯一的村庄中，Ugly Wasp 获得 $563$ 票，Pretty Bee 也获得 $563$ 票。Ugly Wasp 需要严格多于 Pretty Bee 的票数才能获胜，因此 Ugly Wasp 在任何村庄都无法获胜。 由 ChatGPT 4.1 翻译