题解：CF1521D Nastia Plays with a Tree

wl2009_pretty_girl · 2025-06-17 20:00:37 · 题解

不难发现题意可以转化为使用数量最少的链覆盖树上所有点。

这个问题怎么贪都可以，这里介绍一种较短的写法。

具体实现细节见注释。

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second

const int N = 1e5 + 5;
int T, n;
vector<int> v[N];
vector<pair<int, int> > e1, e2;
// e1 存储的是所有要删的边
// e2 存储的是删掉 e1 中的边后所剩的链，不难发现最终 e2 的大小是 e1 + 1 

// dfs 的返回值是经过当前节点的链的底端
// 若返回值为 0，则说明当前节点是某一条链的两个端点的 LCA，即不存在一条经过当前节点的链能够向上拓展 
int dfs(int x, int fa) {
    if (v[x].size() == 1 && v[x][0] == fa) return x;
    int c = 0, nd1 = 0, nd2 = 0;
    for (int y : v[x]) {
        if (y == fa) continue;
        int t = dfs(y, x);
        if (!t) {
            e1.push_back(make_pair(x, y));
            continue;
        }
        // c 不能大于 2，因为一条链只能有两个端点 
        if (c == 2) {
            e1.push_back(make_pair(x, y));
            e2.push_back(make_pair(y, t));
            continue;
        }
        c++;
        if (!nd1) nd1 = t;
        else nd2 = t;
    }
    if (!c) {
        if (x == 1) e2.push_back(make_pair(x, x));
        return x;
    }
    if (c == 1) {
        if (x == 1) e2.push_back(make_pair(x, nd1));
        return nd1;
    }
    e2.push_back(make_pair(nd1, nd2));
    return 0;
}

void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        v[i].clear();
    for (int i = 1, x, y; i < n; i++) {
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    e1.clear(), e2.clear();
    dfs(1, 0);
    cout << e1.size() << '\n';
    for (int i = 0; i < e1.size(); i++)
        cout << e1[i].fi << ' ' << e1[i].se << ' ' << e2[i].se << ' ' << e2[i + 1].fi << '\n';
}

signed main() {
    cin >> T;
    while (T--) solve();
    return 0;
}