Maple and Tree Beauty (Easy Version)

Let the depth of the root be $1$.

For a leaf $v$, its name has length $\text{depth}(v)$. So if

$D=\min_{v\text{ leaf}} \text{depth}(v),$

then the answer is at most $D$. You cannot have a common subsequence longer than the shortest string. That upper bound is brutal and immediate.

So the whole problem becomes:

• can we reach $D$?
• if not, the answer will be $D-1$.

That second bullet sounds suspicious at first, but it is true. More on that after we handle the main test.

What It Means To Reach $D$

Suppose the beauty is $D$. Then there is a binary string $S$ of length $D$ that is a subsequence of every leaf name.

Now look at any leaf with minimum depth $D$. Its name also has length $D$. A length-$D$ subsequence of a length-$D$ string must be the whole string. No deletions, no tricks, no funny business.

So all shortest leaf paths must spell exactly the same string $S$.

For longer leaf paths, $S$ only has to appear as a subsequence. But we can always think of the $i$-th character of $S$ as being matched by some group of vertices, and every root-to-leaf path must hit these groups in order.

The important simplification is this: for checking whether length $D$ is possible, it is enough to use the depth layers themselves as those groups.

That means:

• all vertices at depth $1$ get one shared label;
• all vertices at depth $2$ get one shared label;
• ...
• all vertices at depth $D$ get one shared label.

Then every leaf has the same prefix of length $D$, so the LCS is at least $D$. Since $D$ is already the upper bound, the beauty is exactly $D$.

Why is this not losing anything? If some weird optimal construction matches the subsequence at uneven depths, you can push those matched groups upward. Whenever a vertex at depth at most $D$ is skipped, every leaf below it still needs the remaining matches somewhere in its subtree. Move the earliest needed match in that subtree up to this vertex, and free the old matched vertices below it. This preserves the subsequence order and only makes label-count flexibility better. Repeating this leaves the first $D$ depth layers as the forced groups. So the normal-looking depth-layer construction is not just cute; it is the right thing to test.

Turning Labels Into Knapsack

Let

$c_i = \#\{v : \text{depth}(v)=i\}.$

To force beauty $D$, each group $i\in[1,D]$ must be monochromatic. If depth $i$ is labeled zero, it uses $c_i$ zeros. If it is labeled one, it uses $c_i$ ones.

Let

$S=c_1+c_2+\cdots+c_D.$

The vertices deeper than $D$ do not matter for the common prefix/subsequence of length $D$, so they can receive whatever labels are needed to fix the total count.

So we only need to know which zero counts are possible among the first $D$ depth groups. This is a plain subset sum over weights

$c_1,c_2,\dots,c_D.$

If some subset sum $x$ is possible, then:

• the forced first $D$ layers use $x$ zeros;
• they use $S-x$ ones.

This is compatible with the global requirement of exactly $k$ zeros and $n-k$ ones iff

$x\le k$

and

$S-x\le n-k.$

The remaining $n-S$ deeper vertices can absorb the leftovers. That is literally their job here.

If such an $x$ exists, answer $D$.

Why Otherwise The Answer Is $D-1$

We already know the answer cannot exceed $D$.

If $D$ fails, we claim $D-1$ is always achievable.

Force only depths $1,2,\dots,D-1$ to be monochromatic. Then every leaf shares the same prefix/subsequence of length $D-1$.

Can we always fit the exact number of zeros? Yes.

Before depth $D$, every vertex must have at least one child, otherwise there would be a leaf above depth $D$. Therefore the depth sizes are nondecreasing up to $D$:

$c_1\le c_2\le\cdots\le c_D.$

When we only force the first $D-1$ layers, all vertices from depth $D$ onward are free. In particular, the free pool has size at least $c_D$, which is at least as large as every forced group size.

Now take the forced group sizes in any order and keep adding whole groups as zeros until adding the next group would pass $k$. The previous sum is within one group size of $k$, and one group size fits inside the free pool. So the free vertices can always fill the remaining zeros. That gives an exact labeling with beauty at least $D-1$.

Since $D$ was impossible, the answer is exactly $D-1$.

Algorithm

For each test case:

1. Compute every vertex depth from the parent list.
2. Count children to identify leaves.
3. Let $D$ be the minimum depth among leaves.
4. Count $c_i$, the number of vertices at each depth.
5. Run subset-sum DP over $c_1,\dots,c_D$.
6. If some reachable sum $x$ satisfies $x\le k$ and $S-x\le n-k$, print $D$.
7. Otherwise print $D-1$.

Complexity

The subset sum has total weight at most $n$, so it costs $O(n^2)$ per test case and $O(n)$ memory.

With $n\le 1000$, this is very comfortably fine. No need for bitset wizardry in the easy version.