Editorial for An Animal Contest 7 P2 - Squirrel Structures

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: WilliamWu277

Hint 1

What happens with node $1$ and its children?

Hint 2

$K$ will be at least the number of children node $1$ has $+ 1$ . Because of constraints $2$ and $3$ , neither node $1$ nor its children can be a child of another node.

Solution

It turns out that the minimal $K$ will always be the number of children node $1$ has $+ 1$ . To construct a satisfactory set of $K$ trees, we can set node $1$ and its children as the root of each of the $K$ trees. In order to satisfy constraint $3$ , for each node $i$ that is not already part of a tree we either add it to the tree with node $1$ as root, or the child of node $1$ that is an ancestor of node $i$ as root — meaning we have two choices. This is enough to satisfy constraint $2$ : the remaining nodes can be added to either of those two choices depending on the parity of its depth.

In essence, we just need to add each node to the parent of its parent.

Time Complexity: $\mathcal{O}(N)$

Comments

There are no comments at the moment.