Victorious Coloring (Hard Version)

Turn colorings into constraints

Pick the red vertices and call the set $S$. The cost is

$$x(S)+\delta(S),$$

where $x(S)=\sum_{v\in S}x_v$ and $\delta(S)$ is the total weight of edges with exactly one endpoint in $S$.

So we need minimum $\sum x_v$ such that

$$x(S)+\delta(S)\ge l$$

for every nonempty red set $S$.

Disconnected sets can be ignored. If $S$ has connected components $S_1,S_2,\ldots$, then because the graph is a tree,

$$x(S)+\delta(S)=\sum_i (x(S_i)+\delta(S_i)).$$

One component is no larger than the whole sum, so if every connected set is safe, every disconnected set is safe too.

Which connected sets matter?

Here is the key domination trick.

Take a connected set $S$. Suppose it has an internal edge $e$ and a boundary edge $b$ such that

$$w(e)\le w(b).$$

Delete $e$ from $S$; this splits $S$ into two connected parts. Keep the side that does not contain the endpoint of $b$ inside $S$; call it $T$.

The boundary of $T$ consists of:

• the edge $e$, now leaving $T$,
• the old boundary edges of $S$ that were already touching $T$.

Since $b$ was an old boundary edge on the other side and $w(e)\le w(b)$, we get

$$\delta(T)\le \delta(S).$$

Also $T\subset S$, so $x(T)\le x(S)$. Therefore

$$x(T)+\delta(T)\le x(S)+\delta(S).$$

That means the constraint for $S$ is weaker than the constraint for $T$. In plain English: $S$ is not worth checking.

So after shrinking away all dominated sets, every remaining proper connected set has this property:

every internal edge is heavier than every boundary edge.

Those sets are exactly the components that appear when we process edges from largest weight to smallest.

Build a maximum-Kruskal reconstruction tree:

1. Start with each original vertex as its own component.
2. Sort edges by decreasing weight.
3. When an edge joins two current components, create a new node whose children are those two components.

Every node of this binary tree represents some original connected component $C_v$. Let

$$c_v=\delta(C_v).$$

The root is the whole tree, so $c_{root}=0$.

Why does this cover all important sets? If a connected set has all internal edges heavier than all boundary edges, then all its internal edges are processed before any edge leaving it. At the moment its last internal edge is processed, it becomes exactly one Kruskal component. So it is a node of the reconstruction tree.

Now the original exponential pile of constraints has collapsed to only $2n-1$ constraints:

$$x(C_v)+c_v\ge l.$$

That is the main win. Everything else is implementation pain.

Computing $c_v$

For a leaf $v$, $c_v$ is just the weighted degree of that vertex.

When two components $a$ and $b$ are merged by an edge of weight $w$,

$$c_{new}=c_a+c_b-2w,$$

because that edge used to be counted once in each child boundary, and after merging it becomes internal.

The code computes this with edge contributions:

• add $+w$ to both endpoint leaves,
• add $-2w$ to the merge node,
• then sum children into parents.

For any reconstruction-tree node, internal edges cancel to $0$, and boundary edges contribute exactly once. Clean and nasty, as intended.

Fixed $l$ DP

Let $F_v(l)$ be the minimum total vertex weight needed inside component $C_v$ so that all constraints inside the reconstruction subtree of $v$ are satisfied.

If $v$ has children, their vertex sets are disjoint, so before considering $v$ itself we need

$$\sum_{u\text{ child of }v}F_u(l).$$

Then node $v$ requires

$$x(C_v)\ge l-c_v.$$

If the children already force enough total weight, do nothing. Otherwise add the missing amount anywhere inside $C_v$; extra weight only helps descendants.

Therefore

$$F_v(l)=\max\left(\sum_{u\text{ child of }v}F_u(l),\ l-c_v\right).$$

For leaves, the child sum is $0$, so this is $\max(0,l-c_v)$.

The answer is $F_{root}(l)$.

Hard version: many queries

Doing that DP for every query is $O(nq)$, which is dead on arrival.

Instead, treat $F_v(l)$ as a function of $l$. Every function here is convex and piecewise-linear over integer $l$:

• a leaf is $\max(0,l-c_v)$,
• summing children preserves convex piecewise-linearity,
• taking $\max(G(l),l-c_v)$ also preserves it.

We store each function by slope-change events. An event $(p,d)$ means: starting at integer point $p$, increase the slope by $d$.

To evaluate a queue of events in increasing point order, maintain:

• A: current slope,
• B: value at previous event point,
• pv: previous event point.

When moving to event point p, do

$$B\leftarrow B+A(p-pv),$$

then update the slope.

A leaf $\max(0,l-c)$ is just one event:

$$(c,+1).$$

For an internal node:

1. Merge the two child event queues. This represents $G(l)=F_a(l)+F_b(l)$.
2. Replace it with $$\max(G(l),l-c_v).$$

Merging is small-to-large with priority queues.

Applying the max with a line

Let the current merged function be $G$ and the new line be

$$L(l)=l-c.$$

If $c$ is not before the first breakpoint of $G$, the line never beats $G$ for relevant values. Otherwise, $L$ starts above $G$, and because $G$ is convex and eventually has larger slope, $G$ catches up once.

We pop events while sweeping $G$. On the current segment,

$$G(x)=A(x-pv)+B.$$

Solve the crossing with $x-c$:

$$A(x-pv)+B=x-c,$$

so

$$(A-1)x=A\cdot pv-B-c.$$

If the crossing lies before the next event, we know exactly where the function switches from the line back to $G$.

Since queries are integers, if

$$mid=\left\lfloor\frac{A\cdot pv-B-c}{A-1}\right\rfloor,$$

then:

• up to mid, the line is used,
• from mid+1, $G$ is used.

The three inserted events in the code encode exactly that integer switch. It looks cursed, but it is just floor/ceil bookkeeping. This is the part where off-by-one errors show up with a chair and a baseball bat.

Finally, after building the root function, sort queries by $l$, sweep the root event queue once, and evaluate answers.

Complexity

For each test case:

• building the reconstruction tree: $O(n\log n)$,
• merging priority queues small-to-large: $O(n\log^2 n)$ in the straightforward implementation,
• sorting and answering queries: $O(q\log q+n\log n)$.

Memory is $O(n+q)$.

All answer values fit in long long.