传送门

题解

我们可以想到一个结论：

• 答案 $k \le \left\lceil\dfrac{leaf}{2}\right\rceil$（$leaf$ 为树上的叶子节点的数量）。

证明：对于每一次连边 $(u,v)$，就是连成一个环，让每一个叶子节点两两连边，就形成了一些环，任意删一条边都有其他的路可以走。

注意：随意选根的时候先判一下根是否为叶子节点。

现在，我们考虑如何构造。

如果随意两两连边，就会 WA。

例如：

所以我们不能随意连边。

我们发现对于树中不为根的节点 $u$ 来说，有一个子树里的叶子节点 $\le \left\lfloor\dfrac{leaf}{2}\right\rfloor$（除了链）。

这个也很好证明，当 $u$ 的子树里的叶子节点 $> \left\lfloor\dfrac{leaf}{2}\right\rfloor$，有另一个不为根的节点 $v$ 的子树里的叶子节点 $\le \left\lfloor\dfrac{leaf}{2}\right\rfloor$，得证。

所以，我们可以记录每个节点的 dfn 序，知道对于每个 $u$ 的子树，编号区间为 $(dfn_u,dfn_u + siz_u - 1)$，又知道有一个子树里的叶子节点 $\le \left\lfloor\dfrac{leaf}{2}\right\rfloor$，所以 $dfn_u$ 和 $dfn_u + \left\lfloor\dfrac{leaf}{2}\right\rfloor$ 一定不会在同一个子树。

所以按 dfn 序来排序，最后输出答案即可。

AC code:

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=5e5+5;
int n;
vector<int> g[N];
struct Node{
	int x,y;
	bool operator<(const Node &nd)const{
		return x<nd.x;
	} 
};
vector<Node> leaf;
int dfn[N];
int tim=0;
void dfs(int u,int f){
	dfn[u]=++tim;
	bool cnt=0;
	for(int v:g[u]){
		if(v!=f){
			cnt=1;
			dfs(v,u);
		}
	}
	if(!cnt){
		leaf.push_back({dfn[u],u});
	}
}
signed main(){
	//HAPPY!
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<n;i++){
		int x,y;
		cin>>x>>y;
		g[x].push_back(y);g[y].push_back(x); 
	}
	if(g[1].size()==1){
		leaf.push_back({0,1}); 
	}
	dfs(1,0);
	sort(leaf.begin(),leaf.end());
	int siz=leaf.size();
	cout<<(siz+1)/2<<"\n";
	for(int i=0;i<siz/2;i++){
		cout<<leaf[i].y<<" "<<leaf[i+siz/2].y<<"\n";
	}
	if(siz&1){
		cout<<leaf[siz-1].y<<" "<<leaf[0].y<<"\n";
	}
	return 0;
}