Tree Coloring (Hard Version)

Turn Operations Into Colors

Call operation $1$ color $1$, operation $2$ color $2$, and so on. If a vertex is painted during operation $c$, say its color is $c$.

Then one operation is valid exactly when all vertices in it:

• have different depths;
• contain no parent-child edge.

So we need color all vertices with as few colors as possible such that:

• vertices on the same depth have different colors;
• every vertex has a different color from its parent.

Depth can be counted from $0$ or $1$; only equality of depths matters, so who cares. Classic off-by-one drama, but harmless.

The Lower Bound

There are two unavoidable cliques in the conflict graph.

First, all vertices at the same depth conflict with each other, so if

$W = \max_d |level_d|,$

then we need at least $W$ colors.

Second, take any vertex $v$ and all of its children. The children are all at the same depth, so they pairwise conflict. Also every child conflicts with $v$ by an edge. Therefore this whole set needs distinct colors.

If $child(v)$ is the number of children of $v$, then we need at least

$child(v)+1$

colors for every $v$.

So the answer is at least

$k = \max\left(W,\ 1 + \max_v child(v)\right).$

The nice part: this is also always enough.

Why This Bound Is Enough

We color the tree level by level from the root downward.

Suppose all previous levels are already colored correctly. Now consider one depth level $L$.

Every vertex $u \in L$ has exactly one forbidden color: the color of its parent. We need assign all vertices in $L$ distinct colors, avoiding each vertex's forbidden color.

Since $|L| \le W \le k$, there are enough colors in raw quantity.

The only possible annoying case is when a lot of vertices all forbid the same color. But vertices forbidding some color $c$ are exactly children of the unique vertex on the previous level colored $c$; colors on one level are already distinct. That parent has at most $\max_v child(v) \le k-1$ children.

So no color is forbidden by $k$ vertices on the same level.

That is precisely what we need. If a level has fewer than $k$ vertices, there is slack. If it has exactly $k$ vertices, then not all of them can forbid the same color, because that would mean one parent has $k$ children, which would force at least $k+1$ colors. Not happening with our definition of $k$.

Greedy Construction

For one level, keep the set of unused colors.

Process vertices in any order:

• take the smallest unused color that is not equal to the parent's color;
• remove it from the unused set.

This can only fail if the unused set contains exactly one color, and that color is forbidden by the current vertex.

When that happens, we are at the last vertex of a full level of size $k$. Let the stuck forbidden color be $x$.

Because not every vertex on this level forbids $x$, there is an earlier vertex $y$ whose forbidden color is not $x$.

Swap:

• give the current vertex the color currently used by $y$;
• give $y$ the leftover color $x$.

This is valid because:

• the current vertex gets a color different from $x$;
• vertex $y$ is allowed to take $x$, since its forbidden color is not $x$;
• colors on the level are still distinct.

That's it. No giant matching machinery needed. We bully the one bad case with a swap and move on.

Correctness Proof

Let

$k = \max\left(\max_d |level_d|,\ 1 + \max_v child(v)\right).$

First, $k$ operations are necessary. Every depth level is a clique under the rules, so at least $\max_d |level_d|$ operations are needed. Also, for every vertex $v$, the set containing $v$ and all children of $v$ is a clique, so at least $child(v)+1$ operations are needed. Therefore any answer needs at least $k$ operations.

Now we prove the construction uses exactly $k$ colors and is valid.

During the coloring of one depth level, all assigned colors are chosen from unused colors, so vertices on that level get pairwise distinct colors. We also never assign a vertex its parent's color, except possibly in the stuck case before the swap; after the swap, both affected vertices are valid.

The stuck case can happen only when the current level has size $k$ and only one unused color $x$ remains, with $x$ equal to the current vertex's forbidden color. If all previous vertices also forbade $x$, then all $k$ vertices on this level would be children of the same parent color. Since colors on the previous level are distinct, that means one parent has $k$ children. But then $k \ge child(parent)+1 \ge k+1$, impossible. So some previous vertex forbids a different color, and the swap exists.

Thus every level can be colored. Since parent-child colors differ and same-depth colors differ, every operation group is valid.

The construction uses $k$ colors, and we already proved fewer than $k$ is impossible, so it is optimal.

Complexity

Each vertex is processed once. Set operations cost $O(\log k)$, so the total complexity is

$O(n \log n)$

per total input size, which is easily fine for $2\cdot 10^5$ vertices. Memory is $O(n)$.