题意
给定一颗 $n$ 个节点的树，要求添加尽可能少的边，使得任意删除一条边之后，整个图依然联通。
$3 \leq n \leq 10^5$
题解
首先给出结论：仅需要添加 $\lceil\dfrac m2\rceil$ 条边，其中 $m$ 为叶子节点的数量。构造方法为：从任意一个非叶子节点开始 DFS，按 DFS 顺序给每个叶子节点编号，依次为 $1$ 到 $m$。每次连接叶子 $i$ 和叶子 $i + \lfloor\dfrac m2\rfloor$。
因为每增加一条边，最多会让两个叶子符合要求，因此 $\lceil\dfrac m2\rceil$ 就是下界。
代码
void STRUGGLING([[maybe_unused]] unsigned TEST_NUMBER) {
tp n, rt = 0, leaf = 0; bin >> n;
vector<tp> deg(n + 1, 0), tid(n + 1);
vector<vector<tp>> e(n + 1);
for (tp i = 1; i < n; ++i) {
tp u, v; bin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
++deg[u]; ++deg[v];
}
for (tp i = 1; i <= n; ++i) {
if (deg[i] != 1) rt = i;
}
auto dfs = [&](auto& _, tp x, tp f) -> void {
if (deg[x] == 1) tid[++leaf] = x;
for (auto& i : e[x]) {
if (i != f) _(_, i, x);
}
};
dfs(dfs, rt, rt);
bin << (leaf + 1) / 2 << '\n';
for (tp i = 1; i <= (leaf + 1) / 2; ++i) bin << tid[i] << ' ' << tid[i + leaf / 2] << '\n';
}