2227HUnreviewedunratedGPT-5.4 (high)

Fallen Leaves

Progressive hints first, then the full explanation and implementation when you're ready to cash out.

dfs and similar dp trees

Original problem

Review status

AI-generated and still unreviewed. Double-check the details before internalizing them.

Hints

Progressive nudges

Open only as much as you need to keep the solve alive.

Forget the actual pairing for a second. A pair $(u,v)$ contributes $1$ to every edge on the path between $u$ and $v$ , so the total answer can be rewritten as a sum over edges.

Root the tree. For an edge from a parent to a child $v$ , let $cnt[v]$ be the number of original leaves in the subtree of $v$ . If you must pair an even number of leaves, what parity must the number of pairs crossing that edge have?

Inside a subtree, leaves paired internally disappear in twos. So for an even-size selected set, edge $(p,v)$ must be crossed at least $cnt[v] \bmod 2$ times. A bottom-up greedy pairing shows this lower bound is tight: the edge is crossed exactly once iff $cnt[v]$ is odd.

If the total number of original leaves is odd, exactly one leaf stays unmatched. Pretend you choose that leaf $x$ first and remove it from the set. Then you are back to the even case on $S \setminus \{x\}$ .

Compute $cnt[v]$ for all rooted subtrees and let $base = \sum_{v \ne r} (cnt[v] \bmod 2).$ If the total number of leaves is even, the answer is just $base$ . If it is odd and you remove leaf $x$ , then every edge on the root-to- $x$ path flips parity: odd $\to$ even gives $-1$ , even $\to$ odd gives $+1$ . So $answer = base + \min_{x \in S} \sum_{v \text{ on path } r \to x,\ v \ne r} ((cnt[v]\text{ is even}) ? 1 : -1).$ One DFS for $cnt$ , one DFS for these path sums, done.

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.$

$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$ .

$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$ .

Compute which vertices are original leaves: deg[u] <= 1.
Build a parent array and an order of traversal.
Process vertices in reverse order to get $cnt[v]$ .
Compute $base = \sum_{v \ne 1} (cnt[v] \bmod 2).$
If $cnt[1]$ is even, answer is just $base$ .
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.

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

int main() {
    setIO();

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;

        vector<vector<int>> g(n + 1);
        vector<int> deg(n + 1, 0);

        for (int i = 0; i < n - 1; ++i) {
            int u, v;
            cin >> u >> v;
            g[u].push_back(v);
            g[v].push_back(u);
            deg[u]++;
            deg[v]++;
        }

        int root = 1;

        vector<int> parent(n + 1, -1), order;
        order.reserve(n);
        parent[root] = 0;
        order.push_back(root);

        for (int i = 0; i < (int)order.size(); ++i) {
            int u = order[i];
            for (int v : g[u]) {
                if (v == parent[u]) continue;
                parent[v] = u;
                order.push_back(v);
            }
        }

        vector<int> leaf(n + 1, 0);
        for (int u = 1; u <= n; ++u) {
            leaf[u] = (deg[u] <= 1);
        }

        vector<int> cnt(n + 1, 0);
        ll base = 0;

        for (int i = n - 1; i >= 0; --i) {
            int u = order[i];
            cnt[u] = leaf[u];
            for (int v : g[u]) {
                if (v == parent[u]) continue;
                cnt[u] += cnt[v];
            }
            if (u != root) base += (cnt[u] & 1);
        }

        int totalLeaves = cnt[root];
        if ((totalLeaves & 1) == 0) {
            cout << base << '\n';
            continue;
        }

        vector<ll> pref(n + 1, 0);
        ll best = (ll)4e18;

        for (int u : order) {
            if (leaf[u]) best = min(best, pref[u]);
            for (int v : g[u]) {
                if (v == parent[u]) continue;
                pref[v] = pref[u] + ((cnt[v] & 1) ? -1LL : 1LL);
            }
        }

        cout << base + best << '\n';
    }

    return 0;
}

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

int main() {
    setIO();

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;

        vector<vector<int>> g(n + 1);
        vector<int> deg(n + 1, 0);

        for (int i = 0; i < n - 1; ++i) {
            int u, v;
            cin >> u >> v;
            g[u].push_back(v);
            g[v].push_back(u);
            deg[u]++;
            deg[v]++;
        }

        int root = 1;

        vector<int> parent(n + 1, -1), order;
        order.reserve(n);
        parent[root] = 0;
        order.push_back(root);

        for (int i = 0; i < (int)order.size(); ++i) {
            int u = order[i];
            for (int v : g[u]) {
                if (v == parent[u]) continue;
                parent[v] = u;
                order.push_back(v);
            }
        }

        vector<int> leaf(n + 1, 0);
        for (int u = 1; u <= n; ++u) {
            leaf[u] = (deg[u] <= 1);
        }

        vector<int> cnt(n + 1, 0);
        ll base = 0;

        for (int i = n - 1; i >= 0; --i) {
            int u = order[i];
            cnt[u] = leaf[u];
            for (int v : g[u]) {
                if (v == parent[u]) continue;
                cnt[u] += cnt[v];
            }
            if (u != root) base += (cnt[u] & 1);
        }

        int totalLeaves = cnt[root];
        if ((totalLeaves & 1) == 0) {
            cout << base << '\n';
            continue;
        }

        vector<ll> pref(n + 1, 0);
        ll best = (ll)4e18;

        for (int u : order) {
            if (leaf[u]) best = min(best, pref[u]);
            for (int v : g[u]) {
                if (v == parent[u]) continue;
                pref[v] = pref[u] + ((cnt[v] & 1) ? -1LL : 1LL);
            }
        }

        cout << base + best << '\n';
    }

    return 0;
}

View on Codeforces Back to the list