Hints: Fallen Leaves
Answer to Hint 1: For any unordered pair of vertices $(u,v)$ in a tree, the distance $\mathrm{dist}(u,v)$ equals the number of edges on the unique simple path between them. If you sum $\mathrm{dist}(u,v)$ over several disjoint pairs of leaves, each edge $e$ is counted once for every chosen pair whose path goes through $e$. So the total cost is
$$ \sum_{\text{edges } e} (\text{how many chosen pairs use } e). $$Next: fix a root and relate “who uses edge $e$” to subtree leaf counts.
Fix an arbitrary root $r$. Orient each edge downward from parent to child. Let $\mathrm{cnt}[x]$ be the number of leaves from $S$ that lie in the subtree of $x$ when the tree is rooted at $r$ (include $x$ when $x\in S$).
Temporarily pretend every leaf will be paired (the odd-$|S|$ case will reintroduce exactly one exception). Argue informally how many times a downward edge $(p,c)$ must appear in paired paths, using only parity of $\mathrm{cnt}[c]$.
Answer to Hint 3: Inside child subtree $c$, each leaf matched outside $T_c$ forces its paired path to cross $(p,c)$ exactly once upward; leaves matched inside never use $(p,c)$.
Let $t(c)$ count leaves of $T_c\cap S$ whose partner lies outside $T_c$. Then $\mathrm{cost}=\sum_{\text{edges}(p,c)} t(c)$.
Parity invariant: $t(c)\equiv \mathrm{cnt}[c]\pmod 2$, hence always $t(c)\ge \mathrm{cnt}[c]\bmod 2$.
So every pairing pays at least
$$ B=\sum_{\text{edges}(p,c)} (\mathrm{cnt}[c]\bmod 2). $$Different pairings can overshoot some edges — costs differ — but no one pays below $B$.
Next goal: argue this bound is tight when $|S|$ is even (there exists a pairing costing exactly $B$), then extend when $|S|$ is odd.
What changes when $|S|$ is odd and one leaf remains unchosen?
Let
$$ B=\sum_{\text{edges }(p,c)} (\mathrm{cnt}[c]\bmod 2), $$using the true original $\mathrm{cnt}[\cdot]$.
When $|S|$ is odd, exactly one leaf $x\in S$ never gets paired. Compare the parity pattern of crossings on each edge to the “pretend-even” bookkeeping. Which edges flip between $0$ and $1$ crossings, relative to rooting at $r$?
Answer to Hint 5: Declaring $x$ as the unmatched leaf toggles subtree-parity odd/even along exactly the edges on the root-to-$x$ path (each downward subtree indicator “does subtree contain $x$?” changes exactly once along that chain).
Therefore total cost equals $B$ minus a path-sum objective: along $r\to x$, each edge contributes either $+1$ or $-1$ depending on how its crossing count differs from the baseline parity classification.
Phrase this as maximizing a score $\mathrm{score}(x)$ over leaves $x\in S$.
Make Hint 6 quantitative. For oriented edge $(p,c)$ define
$$ w(p,c)=\begin{cases} +1,&\mathrm{cnt}[c]\text{ odd},\\ -1,&\mathrm{cnt}[c]\text{ even.} \end{cases} $$Set $\mathrm{score}(x)=\sum_{e\in \mathrm{path}(r,x)} w(e)$.
Prove the odd-$|S|$ answer is $B-\max_{x\in S}\mathrm{score}(x)$, while even-$|S|$ answer is just $B$. Outline how to compute $\max_x \mathrm{score}(x)$ in $\mathcal O(n)$.
Answer to Hint 7: Root at $r$. For a vertex $u$, define $\mathrm{best}[u]$ as the maximum, over leaves $x$ lying in the subtree of $u$, of the sum of $w(\cdot)$ along the downward edges of the path $u\to x$ (so $\mathrm{best}[r]=\max_{x\in S}\mathrm{score}(x)$).
Then for a leaf $\ell$ (in the rooted sense) set $\mathrm{best}[\ell]=0$. Otherwise
$$ \mathrm{best}[u]=\max_{\text{children }c\text{ of }u}\bigl(\mathrm{best}[c]+w(u,c)\bigr). $$Finally:
- even $|S|$: print $B$;
- odd $|S|$: print $B-\mathrm{best}[r]$.
(This matches the linear-time reference solution and coincides numerically with model_sol.cpp.)
(Greedy intuition check.) Before coding, sanity-check why several natural greedy pairing orders do not encode this parity invariant — see the editorial section “Greedy approaches that fail.”
(About model_sol.cpp.) It computes the same answer using a $2\times 2$ DP merging children with XOR/additive updates — an equivalent bookkeeping of subtree-parity feasibility plus “best savings along one upward route,” rather than the explicit path-sum formulation above.