Victorious Coloring (Easy Version)

First, kill the annoying part: the red set can be assumed connected.

If the red vertices form several connected components, the total cost is the sum of the costs of those components. Since all vertex weights are nonnegative and edge weights are positive, taking the cheapest component is no worse than taking the whole disconnected set. So

$f(x)=\min_{C\text{ connected, nonempty}}\left(\sum_{u\in C}x_u+\partial(C)\right),$

where $\partial(C)$ is the sum of edge weights crossing from $C$ to outside $C$.

Root the tree anywhere. Let $p_u$ be the weight of the edge from $u$ to its parent, and let $p_{root}=0$.

A DP for fixed vertex weights

For fixed $x$, define $d_u$:

$d_u$ = minimum cost of a connected red subtree fully inside the rooted subtree of $u$, containing $u$, while not counting the parent edge of $u$.

For every child $v$ of $u$, there are only two sane choices:

• do not take anything from $v$'s subtree, then edge $(u,v)$ becomes a boundary edge and costs $w_{uv}$;
• take a connected piece containing $v$, then the best cost is $d_v$.

So:

$d_u=x_u+\sum_{v\text{ child of }u}\min(w_{uv},d_v).$

Any connected red subtree has a unique highest vertex $u$. Its cost is then $d_u+p_u$, because the parent edge is a boundary edge unless $u$ is the root.

Therefore:

$f(x)=\min_u(d_u+p_u).$

So requiring $f(x)\ge l$ is exactly:

$d_u+p_u\ge l\quad\forall u.$

Equivalently:

$d_u\ge \max(0,l-p_u).$

Now optimize backwards

Instead of choosing $x$ directly, choose the resulting values $d_u$.

From the recurrence,

$x_u=d_u-\sum_{v\text{ child of }u}\min(w_{uv},d_v).$

Since $x_u\ge 0$, we need

$d_u\ge \sum_{v\text{ child of }u}\min(w_{uv},d_v).$

Together with the victorious condition, every valid solution must satisfy:

$d_u\ge \max\left(0,l-p_u,\sum_{v\text{ child of }u}\min(w_{uv},d_v)\right).$

The best move is brutally simple: make every $d_u$ as small as possible, bottom-up.

So compute:

$d_u=\max\left(0,l-p_u,\sum_{v\text{ child of }u}\min(w_{uv},d_v)\right).$

Why is this optimal? By induction from leaves upward, every feasible solution has child values at least our values, so its required sum at $u$ is at least ours, so its $d_u$ is at least ours too. Thus our $d$ is componentwise minimum. No hand-wavy greediness. It is forced.

Getting the answer from $d$

The total vertex weight is

$\sum_u x_u=\sum_u\left(d_u-\sum_{v\text{ child of }u}\min(w_{uv},d_v)\right).$

Every non-root $d_u$ appears once positively, and once subtracted from its parent as $\min(p_u,d_u)$. So:

$\sum_u x_u=d_{root}+\sum_{u\ne root}\left(d_u-\min(p_u,d_u)\right).$

That is:

$\boxed{d_{root}+\sum_{u\ne root}\max(0,d_u-p_u)}.$

All values are integers because the recurrence only uses integer max, min, and sum. So the integer restriction causes zero extra pain, which is rare and frankly suspicious, but here it works.

For each query $l$, run one postorder DP over the rooted tree and output the formula above.

Complexity per query: $O(n)$.

Since $q\le 10$ in the easy version and $\sum n\le 250000$, this is easily fine.