题解归档 - cf2227H

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2227H
• 本地来源：problems/cf2227H/idea.md
• 题目链接：https://codeforces.com/contest/2227/problem/H
• 原始标题：cf2227H - Fallen Leaves

思路

cf2227H - Fallen Leaves

pattern: tree metric pairing by edge parity.

claim: the total pairing cost equals the sum over edges of the number of selected leaf-pair paths crossing that edge. For a fixed edge, after cutting it, only the parity of leaf count on one side matters: if that side has odd many paired leaves, exactly one path must cross; otherwise none needs to cross in an optimal pairing.

even leaves: root the tree. For each non-root vertex v, let cnt[v] be the number of original leaves in its subtree. The answer is sum(cnt[v] % 2).

odd leaves: one leaf remains unpaired. If the unpaired leaf lies in subtree v, edge parent[v]-v flips its contribution from cnt[v]%2 to (cnt[v]-1)%2. Therefore choosing a leaf adds -1 on odd-count edges and +1 on even-count edges along the root-to-leaf path. Minimize this path delta over all original leaves.

check: bitmask brute matching on random small trees.

代码

来源：problems/cf2227H/solution.cpp

/* Author: likely
 * Time: 2026-06-27
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        vector<vector<int>>g(n+1);
        for(int i=1;i<n;i++){
            int u,v;
            cin>>u>>v;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        vector<int>par(n+1,0),ord;
        ord.reserve(n);
        par[1]=-1;
        ord.push_back(1);
        for(int i=0;i<(int)ord.size();i++){
            int u=ord[i];
            for(int v:g[u]){
                if(v==par[u]) continue;
                par[v]=u;
                ord.push_back(v);
            }
        }
        vector<int>leaf_cnt(n+1,0),is_leaf(n+1,0);
        int leaves=0;
        for(int i=1;i<=n;i++){
            if((int)g[i].size()<=1){
                is_leaf[i]=1;
                leaves++;
            }
        }
        for(int i=(int)ord.size()-1;i>=0;i--){
            int u=ord[i];
            leaf_cnt[u]+=is_leaf[u];
            if(par[u]>0) leaf_cnt[par[u]]+=leaf_cnt[u];
        }
        ll base=0;
        vector<int>w(n+1,0);
        for(int v=2;v<=n;v++){
            if(leaf_cnt[v]&1){
                base++;
                w[v]=-1;
            }else w[v]=1;
        }
        if(leaves%2==0){
            cout<<base<<"\n";
            continue;
        }
        vector<int>delta(n+1,0);
        ll best=0;
        bool first=true;
        for(int u:ord){
            for(int v:g[u]){
                if(par[v]!=u) continue;
                delta[v]=delta[u]+w[v];
            }
            if(is_leaf[u]){
                if(first||delta[u]<best){
                    best=delta[u];
                    first=false;
                }
            }
        }
        cout<<base+best<<"\n";
    }
    return 0;
}