C 构造

前言

其实开场我已经构造出来了，但是没往构造方面想，反而想一些奇怪的做法。

构造的时候要观察构造的过程，比如你是怎么在草稿纸上画的，怎么转化为数学模型等。

思路

以任意一点为根，进行DFS，求出树的叶集 $L$，叶集的大小为 $m$。

1) 如果m是偶数，那么链必定可以是以下形式 $(u, v)=(L_i,L_{i +\frac{m}{2}})$，但是如果根的度为1，那么需要再加一条链 $(root, L_{k})$。$(k$为任意值$)$

2) 如果m是奇数，那么链为 $(L_i, L_{i + \frac{m + 1}{2}}) $ 和 $(root, L_{i + \frac{m-1}{2}})$

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;

vector<int> leaves, g[N];
vector<pair<int, int>> ans;

void dfs(int u, int fa) {
    bool leaf = true;
    for (int v : g[u]) {
        if (v == fa) continue;
        dfs(v, u);
        leaf = false;
    }
    if (leaf) leaves.emplace_back(u);
}

int main() {
    int n, u, v;
    cin >> n;
    if (n <= 1) {
        cout << "0\n";
        return 0;
    }
    for (int i = 1; i < n; ++i) {
        cin >> u >> v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    dfs(1, 0);

    int m = leaves.size();
    for (int i = 0; i < m / 2; ++i) 
        ans.emplace_back(leaves[i], leaves[i + (m + 1) / 2]);

    if (m % 2 || g[1].size() == 1) 
        ans.emplace_back(1, leaves[m / 2]);
    
    cout << ans.size() << "\n";
    for (auto& p: ans) 
        cout << p.first << ' ' << p.second << '\n';
    
    return 0;
}