题解：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;
}