CTRE - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: pols_agyi_pols
Tester: kingmessi
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

You’re given a tree, each vertex of which must be colored red, blue, or green.
There should be at least one vertex of each color.

The score of a vertex is the sum of the closest vertices to it for each color.
Find the minimum possible sum of scores of the tree.

EXPLANATION:

Let’s think greedily for a bit, and see what our ideal situation would look like.

If a vertex u has (at least) two neighbors, it’d be nice if these two neighbors were different colors (and of course, different from the color of u as well).
For example, if u is colored red, we’d like u to have one blue and one green neighbor.
If this were to happen, the score of u would be 2, which is obviously the best possible.

If u has only one neighbor (i.e u is a leaf), then the ideal situation is instead to have the neighbor of u have a different color, and some neighbor of that neighbor to have the third color.
For instance, if u is red, we can color its neighbor (say v) blue, and then some neighbor of v, green.
The score of u will then be 1+2 = 3, which is again the best we can do for a leaf.

This gives us a lower bound on the answer: if there are K leaves, then the absolute lowest we can hope to get is 3\cdot K + 2\cdot (N-K), with a score of 3 for each leaf and 2 for everything else.

There always exists a coloring that achieves this minimum score!

Construction

Let’s root the tree at some vertex with degree 1.
Then, color each vertex depending on its depth modulo 3: vertices with depth 0, 3, 6, \ldots are colored red, depths 1, 4, 7, \ldots are colored green, and depths 2, 5, 8, \ldots are colored blue.

Now,

  • Any non-leaf vertex has a different color from its parent and its children; and the parent’s color doesn’t equal the child’s.
    The score of all non-leaf vertices is thus 2.
  • Any leaf vertex (ignoring the root) has a different color from its two immediate ancestors, and so has a score of 3.
  • The root has two different colors at depths 1 and 2, and hence also obtains a score of 3.

This matches our lower bound, and is hence optimal.

All that’s needed is to count the number of leaves, which is easy enough - store the degrees of every vertex, and count the number of them with degree 1.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n = int(input())
    deg = [0]*n
    for i in range(n-1):
        u, v = map(int, input().split())
        deg[u-1] += 1
        deg[v-1] += 1
    leaves = 0
    for i in range(n): leaves += deg[i] == 1
    print(3*leaves + 2*(n - leaves))