翻译好评。
原题传送门
题意简化
给定一颗 \text{n} 个点的无根树，求最少加多少条边使形成的图任意删除一条边后都联通，边是无向的。
输出最少加边数和任意一种加边方案。
一道不错的构造题。
首先显然连接的边都是叶子肯定不会比其它方案要劣。
如果这个图是个环，那么断一条边就不会使此图不连通。所以选两个叶节点连接最优。这使得环上节点最多。
于是问题转换为选出尽量少的起点和终点都是叶子节点的路径覆盖完树上所有边。
这种题可以尝试证明答案的上/下界然后对着构造。这题假设叶子节点有 \text{m} 个，显然答案不会小于 \lceil \frac{m}{2} \rceil 。因为每个叶子都需要一条边来使其与父亲双联通。
考虑构造一个答案为 \lceil \frac{m}{2} \rceil 的解。
假如我们选取了一个节点 \text{x} 作为根，我们希望每个叶子都能和一个与它不属于同一棵（根节点儿子为根）子树的叶子匹配。
令 a_k 表示其各个儿子节点子树内的叶子个数。我们相当于每次选择一组非零的 a_i , a_j 将它们都减 1，表示这两个子树内选择两个叶子匹配，执行到最后如果剩下了一个 1 就将其随便和一个其它子树的叶子匹配。
显然当最大的 a_i 的两倍超过 \sum{a_i} 时就不存在任何可行方案。那么我们就找一个类似“重心”的点（只不过是子树大小改为子树叶子个数）作为根，然后每次贪心地选取最大的一组 a_i, a_j 去匹配，各自减 1 放回去，直到无法执行就好了。
为什么这样一定能出解呢？考虑归纳证明，选取最大的 a_i, a_j 都减 1 塞回去，
然后边界情况两个 $1$ 是显然成立的。证毕。时间复杂度 $\text{O(nlogn)}$。
---
由于`dfs`的性质，我们搞出所有叶子节点后掐头掐尾即可完成匹配。即**每个叶子都能和一个与它不属于同一棵（根节点儿子为根）子树的叶子匹配。**
记得要选一个非叶节点作为根跑`dfs`。
可能大家听得云里雾里，放一下代码给大家参考吧。
```cpp
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int N=5e5+10;
int n,fir[N],tot,du[N],leaf[N],cnt;
struct node {int to,nex;} e[N << 1];
void add(int u,int v)
{
e[++tot].to=v;
e[tot].nex=fir[u];
fir[u]=tot; du[v]++;
return ;
}
void dfs(int x,int dad)
{
bool f=true;
for(int i=fir[x];i;i=e[i].nex)
if(e[i].to^dad) {f=false; dfs(e[i].to,x);}
if(f) leaf[++cnt]=x;
return ;
}
int main()
{
// freopen("work.in","r",stdin); freopen("work.out","w",stdout);
scanf("%d",&n);
for(int i=1,u,v;i<n;i++)
{
scanf("%d%d",&u,&v);
add(u,v); add(v,u);
}
int root=0;
for(int i=1;i<=n && !root;i++) if(du[i] > 1) root=i;
if(!root) return printf("1"),0;//边界
dfs(root,0);
printf("%d\n",(cnt+1)>>1);
for(int i=1;i<=cnt>>1;i++) printf("%d %d\n",leaf[i],leaf[i+(cnt>>1)]);
if(cnt&1) printf("%d %d",leaf[(cnt>>1)+1],leaf[cnt]);
// fclose(stdin); fclose(stdout);
return 0;
}
```
感谢阅读！您的点赞和评论是对作者最大的支持!