Maple and Tree Beauty (Hard Version)

Let the root have depth $0$, and define

$D=\min_{v\text{ is a leaf}} depth_v.$

Some leaf name has length exactly $D+1$, so no common subsequence of all leaf names can be longer than $D+1$.

The whole problem is deciding whether this upper bound is possible. If yes, the answer is $D+1$. If no, the answer is $D$. That is the main trap: do not try to run LCS DP on a tree. That way lies sadness.

Checking whether $D+1$ is possible

Suppose we want a common subsequence

$s_0s_1\dots s_D$

of length $D+1$.

A clean way to guarantee it is:

• label every vertex at depth $0$ with $s_0$,
• label every vertex at depth $1$ with $s_1$,
• ...
• label every vertex at depth $D$ with $s_D$.

Then every root-to-leaf path begins with exactly this string, so the LCS has length at least $D+1$. Since $D+1$ is already the upper bound, this is optimal.

The important structural fact is that considering these depth layers loses no power. Any length-$(D+1)$ common subsequence can be viewed as choosing one ordered same-label group for each subsequence character. If some vertex in the first $D+1$ layers is skipped, then some descendant in its subtree must be doing the job for the relevant group. Moving that choice upward to the skipped vertex cannot make the label-count constraint worse; it only replaces a more awkward deeper choice with a layer choice. Repeating this gives the layer construction.

So only the sizes of the first $D+1$ depth layers matter.

Let

$c_i = \#\{v : depth_v=i\}, \quad 0\le i\le D,$

and

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

If depth $i$ is labeled $0$, it consumes $c_i$ zeros. If it is labeled $1$, it consumes $c_i$ ones. The vertices deeper than $D$ do not affect this common prefix, so they can absorb whatever labels are left.

Therefore $D+1$ is achievable iff there is a subset sum

$x=\sum_{i\in A} c_i$

such that

$x\le k$

and

$S-x\le n-k.$

The first inequality says the zero-labeled important layers fit inside the zero budget. The second says the one-labeled important layers fit inside the one budget. Everything deeper is flexible filler.

Why $D$ is always achievable if $D+1$ is not

Use only depths $0,1,\dots,D-1$ for the common subsequence.

For every $i<D$, every vertex at depth $i$ has a descendant at depth $D$, because no leaf exists above depth $D$. Hence

$c_i\le c_D.$

When assigning labels to layers $0$ through $D-1$, at least one label pool has enough remaining labels for the current layer. If both zeroes and ones had fewer than $c_i$ labels left, together they would have fewer than $2c_i$ labels, but the current layer plus the still-unassigned depth-$D$ layer already need at least $c_i+c_D\ge 2c_i$ vertices. Contradiction. So length $D$ is always doable.

Subset sum optimization

We need subset sums of the multiset

$c_0,c_1,\dots,c_D.$

The total sum is at most $n$. Group equal weights. If weight $w$ appears $m$ times, replace those $m$ copies with binary chunks, for example:

$13w = 1w+2w+4w+6w.$

This preserves all possible counts from $0$ to $m$ copies of weight $w$, but uses only $O(\log m)$ items.

Then run bitset knapsack:

$dp \mathrel{|}= dp \ll item.$

Finally scan reachable sums $x$ in the valid range

$\max(0,k-(n-S))\le x\le \min(k,S).$

If one is reachable, print $D+1$; otherwise print $D$.

The memory is $O(n)$, and the compressed bitset transitions are easily fast enough for the hard constraints.