Miss Punyverse
Contest: Codeforces Round 607 (Div. 1)
Difficulty rating: 2500
Tags: dp, greedy, trees

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.

Input format:
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$$$.

Output format:
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.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Note:
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.

Example input:
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

Example output:
2
0

Editorial:
Let's say a region is winning if there are strictly more wasps than bees. Thus, we're maximizing the number of winning regions.
Tree DP seems natural in this sort of situation. For example, after rooting the tree arbitrarily, you could probably come up with something like $$$f(i, r)$$$: Given the subtree rooted at $$$i$$$ and the number of regions $$$r$$$, find the maximum number of winning regions if we partition that subtree into $$$r$$$ regions. However, this has an issue: we also need to merge our topmost component with the topmost component of some subtrees, so the subtrees' vote advantage at their topmost components matter, and must also be considered in the DP. Unfortunately, if we just naively insert the vote advantage to our DP state (or output), this means that there could potentially be too many states/outputs to fit in the time limit.
Fortunately, we can keep the number of states the same by using the following greedy observation: It is optimal to maximize the number of winning regions first, and then to maximize the vote advantage at the top second. In other words, in a subtree, $$$$$$(\text{$x$ winning regions}, \text{$-\infty$ vote advantage})$$$$$$ is better than $$$$$$(\text{$x-1$ winning regions}, \text{$+\infty$ vote advantage}).$$$$$$ This is because the $$$+\infty$$$ vote advantage at the top component, at best, can increase the number of winning regions by $$$1$$$, but we can already guarantee to achieve that with $$$(x, -\infty)$$$.
So the DP now becomes $$$f(i, r)$$$: Given the subtree rooted at $$$i$$$ and the number of regions $$$r$$$, find the maximum number of winning regions, and among all such possibilities, find the maximum vote advantage of the top component.
Just be careful that your DP solution doesn't construct size-$$$0$$$ partitions.
Now, what about the time complexity? We have a state that looks like $$$(i, r)$$$, where $$$1 \le r \le \mathit{size}(i)$$$, and a transition that runs in $$$O(r)$$$, so naively it feels like it runs in $$$O(n^3)$$$ in the worst case. However, if you've seen this before, this is actually the sort of DP pattern that is really $$$O(n^2)$$$, at least with the right implementation.
Specifically, if we ensure that we only loop across the range where the substates are both valid, then you may check that the total amount of work done in each node is $$$O\left(\mathit{size}(i)^2 - \sum\limits_{\text{$$$j$$$ is a child of $$$i$$$}} \mathit{size}(j)^2\right)$$$, and such a recurrence can be analyzed to be $$$O(n^2)$$$.