Fallen Leaves

Observation 1: stop thinking about matchings

This looks like some nasty matching problem on leaves. On a general graph, sure, that would suck. But on a tree, every pair is just a path.

If $x_e$ is the number of chosen pairs whose path uses edge $e$, then

$answer = \sum_e x_e.$

So the whole game is: for each edge, how many pairs are forced to cross it?

Even number of leaves

Fix any root $r$. For every non-root vertex $v$, let $cnt[v]$ be the number of original leaves in the subtree of $v$.

Look at the edge between $v$ and its parent. Suppose all leaves must be paired.

Let $x_v$ be the number of pairs with exactly one endpoint inside the subtree of $v$. After those $x_v$ leaves leave the subtree, every remaining leaf inside it must be paired internally. That means

$cnt[v] - x_v \equiv 0 \pmod 2.$

So

$x_v \equiv cnt[v] \pmod 2,$

hence in particular

$x_v \ge cnt[v] \bmod 2.$

That is a lower bound for each edge.

Now the nice part: it is tight.

Do a bottom-up greedy process:

• each child subtree pairs as much as possible internally;
• it sends one unpaired leaf upward iff it contains an odd number of leaves;
• at the current node, pair all received leaves arbitrarily, and if one remains, send it upward.

So each subtree sends at most one leaf through its parent edge, and it does so exactly when its leaf count is odd. Therefore the minimum cost for an even number of leaves is

$answer = \sum_{v \ne r} (cnt[v] \bmod 2).$

Yep. Just parity. The scary matching was mostly fake news.

Odd number of leaves

If the total number of leaves is odd, exactly one original leaf stays unmatched. Suppose that leaf is $x$.

Then we remove $x$ from consideration and pair all leaves in $S \setminus \{x\}$. That set has even size, so the previous formula applies.

For a vertex $v$, the new number of leaves in its subtree becomes:

• $cnt[v] - 1$ if $x$ lies in the subtree of $v$;
• $cnt[v]$ otherwise.

So the cost for leaving $x$ unmatched is

$cost(x) = \sum_{v \ne r} ((cnt[v] - I_v(x)) \bmod 2),$

where $I_v(x)$ is $1$ iff $x$ is in the subtree of $v$.

Now comes the key simplification.

The vertices whose subtree contains $x$ are exactly the vertices on the root-to-$x$ path, excluding the root. So only those edges change.

Let

$base = \sum_{v \ne r} (cnt[v] \bmod 2).$

For a vertex on the root-to-$x$ path:

• if $cnt[v]$ is odd, its contribution flips $1 \to 0$, so delta is $-1$;
• if $cnt[v]$ is even, its contribution flips $0 \to 1$, so delta is $+1$.

So

$cost(x) = base + \sum_{v \text{ on path } r \to x,\ v \ne r} (1 - 2 \cdot (cnt[v] \bmod 2)).$

Therefore, when the total number of leaves is odd, we just need the minimum root-to-leaf path sum with edge weight

$w[v] = 1 - 2 \cdot (cnt[v] \bmod 2).$

That is $+1$ for even $cnt[v]$, and $-1$ for odd $cnt[v]$.

How to compute it in linear time

Root the tree at vertex $1$.

1. Compute which vertices are original leaves: deg[u] <= 1.
2. Build a parent array and an order of traversal.
3. Process vertices in reverse order to get $cnt[v]$.
4. Compute $base = \sum_{v \ne 1} (cnt[v] \bmod 2).$
5. If $cnt[1]$ is even, answer is just $base$.
6. Otherwise, do one more pass from the root:
   • pref[1] = 0
   • for every child to of v, $pref[to] = pref[v] + (cnt[to] \text{ odd } ? -1 : +1).$
   • among all original leaves $x$, minimize $pref[x]`.

Then

$answer = base + \min_{x \in S} pref[x].$

Correctness sketch

• For an even-size chosen leaf set, every subtree must send upward a number of leaves with the same parity as its leaf count. So every parent edge contributes at least $cnt[v] \bmod 2$.
• The bottom-up greedy pairing achieves exactly that bound on every edge simultaneously.
• For an odd total number of original leaves, fixing the unmatched leaf $x$ turns the problem into the even case on $S \setminus \{x\}$.
• Removing $x$ flips the parity exactly on the root-to-$x$ path, which gives the path-sum formula above.
• Minimizing over leaves gives the optimal unmatched leaf, hence the global optimum.

Complexity

Each edge is processed a constant number of times.

• building the rooted tree: $O(n)$
• computing $cnt$: $O(n)$
• computing the best path sum: $O(n)$

So each test case runs in

$O(n),$

and over all test cases the total complexity is

$O\left(\sum n\right),$

with $O(n)$ memory.

Clean, fast, and no cursed heavy DP tables. Just parity doing parity things.