Coloring a Red Black Tree

1. Kill the useless randomness

Operating on a red vertex is never helpful. It either stays red or becomes black. That is strictly worse, because having more red vertices can only help: you can always ignore the extra red vertices and simulate any strategy.

So in an optimal strategy we only operate on black vertices. Then the red set only grows.

If a black vertex $v$ currently has $k$ red neighbors, one operation on $v$ succeeds with probability

$$p=\frac{k}{\deg(v)}.$$

If it fails, a black neighbor was chosen, so $v$ remains black and the entire state is unchanged. Therefore the expected number of operations needed to make $v$ red right now is

$$\frac{1}{p}=\frac{\deg(v)}{k}.$$

The stochastic process has been mugged in an alley and replaced by an ordering problem.

We need choose an order in which initially black vertices become red. If vertex $v$ has $k_v$ red neighbors before it is colored, its contribution is

$$\frac{\deg(v)}{k_v}.$$

2. Split into black components

Remove all initially red vertices. The remaining black vertices form a forest. Different black components do not interact, because initially red vertices are permanent sources and we never operate on them.

For a black vertex $v$, define:

• $d_v = \deg(v)$ in the original tree,
• $c_v =$ number of initially red neighbors of $v$.

Now consider one black component, which is a tree.

Given an order of coloring its vertices, orient every black-black edge from the earlier colored endpoint to the later colored endpoint. Then every incoming black edge into $v$ represents one black neighbor that was already colored red before $v$.

So the cost becomes

$$\sum_v \frac{d_v}{c_v + \operatorname{indeg}(v)}.$$

Conversely, any orientation of a tree is acyclic. If every vertex has

$$c_v + \operatorname{indeg}(v) > 0,$$

then a topological order of this orientation is a valid coloring order. Sources must have $c_v>0$, so they can start from initial red neighbors.

Thus we need minimize

$$\sum_v \frac{d_v}{c_v + \operatorname{indeg}(v)}$$

over orientations of each black tree.

3. Tree DP over orientations

Root a black component arbitrarily.

Let

$$dp_v[t]$$

be the minimum total cost inside the subtree of $v$, where $t\in\{0,1\}$ tells whether the parent edge contributes an incoming edge to $v$:

• $t=1$: parent edge is oriented parent $\to v$, so parent is earlier and contributes $1$ to $v$'s denominator.
• $t=0$: parent edge does not contribute to $v$.

For a child $u$ of $v$, there are two choices:

1. Orient $v\to u$. Then $u$ gets its parent contribution, so we pay $dp_u[1]$.
2. Orient $u\to v$. Then $v$ gains one incoming edge, and $u$ does not get parent contribution, so we pay $dp_u[0]$.

If $S$ is the set of children oriented into $v$, then

$$dp_v[t] = \min_S \left( \frac{d_v}{c_v+t+|S|} + \sum_{u\in S} dp_u[0] + \sum_{u\notin S} dp_u[1] \right),$$

with the condition

$$c_v+t+|S|>0.$$

For fixed $x=|S|$, we should choose the $x$ children with smallest extra cost

$$\Delta_u = dp_u[0]-dp_u[1].$$

So for each vertex:

1. collect all child deltas,
2. sort them,
3. use prefix sums,
4. try every possible number $x$ of children pointing into $v$.

The root has no parent, so its contribution is $dp_{root}[0]$.

4. Complexity

Each black-black edge contributes to exactly one delta list. Sorting all child lists costs

$$O\left(\sum_v \deg(v)\log \deg(v)\right)=O(n\log n).$$

Memory usage is

$$O(n).$$

Good enough. No drama, no Monte Carlo nonsense, no praying to floating-point gods beyond normal doubles/long doubles.