题解：CF1092E Minimal Diameter Forest

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,x,y,pos=1,d[200005];
vector<int>g[200005];
void dfs(int u,int fa){
	d[u]=d[fa]+1;
	if(d[u]>d[pos])pos=u;
	for(int i:g[u]){
		if(i!=fa)dfs(i,u);
	}
}
signed main () {
	cin>>n;
	for(int i=1;i<n;i++){
		scanf("%lld%lld",&x,&y);
		g[x].push_back(y);
		g[y].push_back(x);
	}
	dfs(1,0);
	dfs(pos,0);
	cout<<d[pos]-1;
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pii;
int t,n,m,x,y,fa[1005],d[1005],pos,len[1005],cen[1005],cnt,s,maxa=-1e9;
vector<int>g[200005];
vector<pii>ans;
bool vis[200005];
int find(int x){
	if(fa[x]==x)return x;
	return fa[x]=find(fa[x]);
}//每棵树的分类 
void dfs(int u,int fa){
	d[u]=d[fa]+1;
	if(d[u]>d[pos])pos=u;
	for(int i:g[u]){
		if(i!=fa)dfs(i,u);
	}
}//求直径 
void get(int u,int fa,int halflen){
	if(d[u]-1==halflen){
		cnt=u;
		return ;
	}
	for(int i:g[u]){
		if(i!=fa)get(i,u,halflen);
	}
}//求中点 
signed main () {
	cin>>n>>m; 
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1;i<=m;i++){
		scanf("%lld%lld",&x,&y);
		g[x].push_back(y);
		g[y].push_back(x);
		fa[find(x)]=find(y);
	}
	for(int i=1;i<=n;i++){
		if(!vis[find(i)]){
			vis[find(i)]=1;
			pos=find(i);
			dfs(find(i),0);
			dfs(pos,0);
			len[find(i)]=d[pos]-1;//len是每棵树的直径 
			cnt=find(i);
			get(pos,0,len[find(i)]/2);
			cen[find(i)]=cnt;//每棵树的直径的中点 
			if(len[find(i)]%2==0)x=len[find(i)]/2;
			else x=len[find(i)]/2+1;//直径长度的奇偶性需要分类讨论，但是长度为奇数时选择两个点作为根都是一样的 
			if(x>maxa){
				maxa=x;
				s=cen[find(i)];
			} 
		} 
	} //找每棵树直径的中点 ,s是所有树的根集中的那一点 
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;i++){
		if(!vis[find(i)]){
			vis[find(i)]=1;
			if(cen[find(i)]!=s){
				g[cen[find(i)]].push_back(s);
				g[s].push_back(cen[find(i)]);
				ans.push_back({s,cen[find(i)]});//连每棵树的根，并记录答案 
			}
		}
	} 
	pos=1;
	dfs(1,0);
	dfs(pos,0);//再次求直径 
	cout<<d[pos]-1<<endl;
	for(pii i:ans)cout<<i.first<<" "<<i.second<<endl;
	return 0;
}