Tree Coloring (Easy Version)

Call each operation a color. If two vertices receive the same color, they are colored in the same operation.

The operation rule becomes:

• vertices at the same depth must have different colors;
• adjacent vertices must have different colors.

Because the tree is rooted, every edge is between a vertex and its parent/child. So we need the minimum number of colors for this special coloring.

A tempting wrong idea is: "just take the widest depth level." Nope. A star with root $1$ and $n-1$ children has widest level $n-1$, but the root conflicts with every child, so the answer is $n$. Width alone gets drop-kicked immediately.

Lower bounds

Let $L_h$ be the set of vertices at depth $h$.

First, all vertices in one level $L_h$ have the same distance from the root, so no two of them can be in the same operation. Therefore we need at least

$$\max_h |L_h|$$

colors.

Second, take any vertex $v$ with $c_v$ children. The set consisting of $v$ and all its children also needs all different colors:

• $v$ is adjacent to every child;
• all children of $v$ are on the same depth, so they conflict with each other too.

So we need at least

$$\max_v (c_v+1)$$

colors.

Thus the answer is at least

$$K=\max\left(\max_h |L_h|,\max_v(c_v+1)\right).$$

The only remaining question is whether some nasty combination of constraints between neighboring levels forces more than $K$. It does not.

Why $K$ colors are enough

We prove that the tree can always be colored level by level using $K$ colors.

Assume level $L_h$ is already colored, and all colors inside that level are distinct. Now color level $L_{h+1}$.

Each vertex $u\in L_{h+1}$ has exactly one forbidden color: the color of its parent. Besides that, it can use any of the $K$ colors. Also, all vertices of $L_{h+1}$ must receive distinct colors.

This is a matching problem:

• left side: vertices of $L_{h+1}$;
• right side: the $K$ colors;
• a vertex connects to every color except its parent's color.

We need to match every vertex on the next level to a distinct allowed color.

Check Hall's condition. Take any subset $X$ of vertices from $L_{h+1}$.

If all vertices in $X$ have the same forbidden color, then they all have the same parent, because the previous level uses distinct colors. They have $K-1$ available colors. That parent has at most $K-1$ children since $K\ge c_v+1$, so

$$|X|\le K-1.$$

Good.

If vertices in $X$ have at least two different forbidden colors, then their union of allowed colors is all $K$ colors. Any color forbidden by one of them is allowed by another one with a different forbidden color. Also the whole next level has size at most $K$, so

$$|X|\le |L_{h+1}|\le K.$$

Good again.

Hall's condition holds, so the next level can be colored. Starting from the root and repeating this for every depth colors the whole tree with $K$ colors.

Therefore the minimum number of operations is exactly

$$\boxed{\max\left(\max_h |L_h|,\max_v(c_v+1)\right)}.$$

Implementation

Root the tree at vertex $1$ using BFS or iterative DFS.

During traversal, compute:

• $depth[v]$;
• $c_v$, the number of children of $v$ in the rooted tree;
• $|L_h|$, the number of vertices at each depth.

Then output

$$\max\left(\max_h |L_h|,\max_v(c_v+1)\right).$$

The note uses root depth $1$ instead of the usual $0$. That changes absolutely nothing; only equality of depths matters. Classic indexing nonsense, harmless.

Complexity is $O(n)$ per test case, with $O(n)$ memory.