场上糊了一个小时都没糊出来（我甚至写了个假算法前半个多小时还没找到反例）
因为题目最后要求我们得到的是一条链，删除的边的数量和加边的数量一样多，所以我们要让删除的边最少。又因为我们要得到的一条链肯定是由多条组合起来的，而原树是由多条链构成的，我们最少要删除链数-1条边，那么问题转换成了如何把树划分成最少的链数。
考虑用贪心解决，在dfs到某个点u的时候，先处理u的子树，得到了一些仍然在和u连接的子节点，
1. 如果子节点的数量为1，那么就继续把这个链往上传。
2. 如果=2，就把这两个子节点合并成一条链，并把u和u的父亲断开
3. 如果>2，就把某两个节点合并成一条链，剩下的拆成一条一条的链
为什么这样是最优的呢，我们希望当前点u对u的父亲影响尽可能的小，所以在=2的时候，既然一定是把某两个点之间分离，变成两条不同的链，那把两个子节点合并成一条链，可以让u的父亲度数-1，让u的父亲有可能划分出更少的链，>2的时候也是同理。
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10; vector < int > edge[N]; vector < tuple <int, int, int, int> > ans; int md; int dfs(int x, int f) { int ch = 0, t = x; for (int u:edge[x]) { if (u == f) continue; int v = dfs(u, x); if (!v) continue; ch++; if (ch == 1) t = v; else if (ch == 2) ans.emplace_back(x, f, v, md), md = t; else ans.emplace_back(u, x, u, md), md = v; } return (ch <= 1) ? t : 0; } int main() { int T; scanf("%d", &T); while (T--) { int n; scanf("%d", &n); for (int i = 1; i < n; i++) { int x, y; scanf("%d%d", &x, &y); edge[x].push_back(y); edge[y].push_back(x); } md = 1; while (edge[md].size() != 1) md++; dfs(md, 0); printf("%d ", ans.size()); for (auto [a, b, c, d]:ans) printf("%d %d %d %d ", a, b, c, d); ans.clear(); for (int i = 1; i <= n; i++) edge[i].clear(); } return 0; }