### PROBLEM LINK:

**Author:** Praveen Dhinwa

**Tester:** Kevin Atienza

**Editorialist:** Kevin Atienza

### PREREQUISITES:

Greedy algorithms

### PROBLEM:

Given a tree, a **nice node** is any node with degree \ge 3. The **niceness** of a tree is the maximum number of *removals* one can do to a tree before it gets emptied. A **removal** in a tree is the following procedure:

- Identify all the nice nodes.
- Remove all nodes such that there is a path to a leaf that does not pass through a nice node.

Given an N and \mu, is there a tree with exactly N nodes and exactly \mu niceness?

### QUICK EXPLANATION:

If there’s a tree with N nodes and niceness \mu, then there is also a tree with N+1 nodes and niceness \mu (by just attaching a new node to a leaf). Therefore, we only need to find, for each \mu, the minimum number of nodes required to achieve a niceness of \mu. Let’s denote this by M(\mu).

It turns out that a greedy algorithm works:

- For \mu = 1, the answer is a one-node tree.
- To get an optimal tree with \mu niceness, first take an optimal tree with \mu-1 niceness and turn all leaves into nice nodes by attaching leaves to them. If \mu = 2, then you have to attach three leaves. If \mu > 2, you have to attach two leaves.

One can work out that M(\mu) = 3\cdot 2^{\mu-1}-2. Therefore, the answer is `Yes`

if N \ge M(\mu), and `No`

otherwise. Be careful with overflow!

### EXPLANATION:

# Removal

Let us first understand what a “removal” actually does. Let’s assume for simplicity that N > 1 (there is only one tree with N = 1 anyway). Therefore, we can assume that all nodes have at least one degree.

What does it mean to have a path to a leaf not passing through a nice node? Of course, the node must not be nice itself. Therefore, its degree is either 1 or 2. If the degree is 1, then the node is a leaf, so it will be removed during the removal. If the degree is 2, then there are two paths that can be followed. We find the first node along each path that is not of degree 2. If one of them meets a degree 1 node, then the path towards that node constitutes a “path to a leaf that does not pass through a nice node”, and thus the node is removed. If both paths arrive at degree > 2 nodes, then those nodes are nice nodes, and thus all paths to leaves must pass through a nice node, and the node is not removed

The above now describes completely which nodes will be removed at the current removal step:

- If there are no nice nodes, then the whole tree is a simple path, and all nodes are removed.
- If there is at least one nice node, then the nodes lying on “dangling” paths attached to nice nodes are removed.

# Trees with a given niceness

Next, let’s try to answer whether there is a tree with N nodes and a niceness of \mu. The first thing we notice is that we can increase the number of nodes without changing the niceness: by attaching a new node to any leaf! Therefore, we have the property that:

*If there is a tree with N nodes and a niceness of \mu, then there is also a tree with N+1 nodes and a niceness of \mu.*

This means that there exists a tree with N nodes and niceness \mu if and only if N is not less than the size of the smallest tree with niceness \mu, and thus we only need to know for any fixed \mu the minimum number of nodes to achieve a niceness of \mu. Let M(\mu) be this minimum. We will now describe M(\mu) in the next section.

# Calculating M(\mu)

One can probably try by hand (or with a bruteforcer) to get the following values:

The corresponding trees are something like the following:

To extend this to larger trees, you get the idea: to get the optimal tree of niceness \mu, take the optimal tree of niceness \mu-1 and attach two leaves for every leaf! (In the case of \mu = 2, attach *three*.) This gives a somewhat small tree of niceness \mu with 3\cdot2^{\mu-1}-2 nodes. But are these trees really the smallest? Well, if you don’t have any formal proof yet, one important thing to remember during programming contests is to have a reasonable faith in your intuition. If you believed enough that this is optimal (which it seems intuitively) and submit this solution, you’ll get accepted!

However, it is still important to discuss whether this is really optimal. In the next section we will prove this.

# Proof that optimal trees are optimal

Let’s try to prove that M(\mu) = 3\cdot 2^{\mu-1} - 2. Clearly, we know that M(\mu) \le 3\cdot 2^{\mu-1} - 2, because we have examples of such trees using the construction above. It remains to show that M(\mu) \ge 3\cdot 2^{\mu-1} - 2. For \mu = 1, this is clear, so we will only focus on \mu \ge 2. We will prove this by induction; specifically we will prove the following statement:

**For any \mu \ge 2, any tree with niceness \mu has at least 3\cdot 2^{\mu-1} - 2 nodes and 3\cdot 2^{\mu-2} leaves.**

For the base case \mu = 2, there cannot be only two leaves, because a tree with two leaves is just a path, and it only has a niceness of 1. Therefore there must be at least 3 = 3\cdot 2^{\mu-2} leaves. Next, any graph with < 4 nodes only has at most two leaves, therefore our tree must have at least 4 = 3\cdot 2^{\mu-1} - 2 nodes.

For the inductive case, assume that we have proven the statement for \mu, and we want to prove it for \mu + 1. Suppose we have a tree of niceness \mu + 1. If we perform a single removal step, then we will end up with a graph with niceness \mu, and by induction it has at least 3\cdot 2^{\mu-1} - 2 nodes and 3\cdot 2^{\mu-2} leaves. However, all of these leaves must have been nice nodes before the removal step, otherwise they should have been removed. Therefore, there must be at least two other branches attached to each leaf before, and each of these branches had at least one leaf, so our original graph must have had at least (3\cdot 2^{\mu-2})\cdot 2 = 3\cdot 2^{\mu-1} leaves. Thus the number of nodes must have been at least (3\cdot 2^{\mu-1} - 2) + (3\cdot2^{\mu-1}) = 3\cdot 2^{\mu} - 2, which proves the inductive case

### Time Complexity:

O(\log \mu)

### AUTHOR’S AND TESTER’S SOLUTIONS:

Will be uploaded soon.