题解
下文将“以该节点为根时树的最大深度最小”的节点称为“最小节点”，并将“以最小节点为根时树的最大深度”称为“最小深度”。
题目给出的是无根树森林，易得对于每一棵树来说，使“最小节点”与其他树连接最优。而最终方案则是将所有树与“最小深度”最大（或第二大）的树建边，证明：
设树(A,B,C)的“最小深度”分别为(x,y,z(x<y<z))，若将(y,z)分别与(z)树的“最小节点”连边，则直径最小为(min(y+z+2,x+y+1,x+z+1)=y+z+2)；而将(x,y)分别与(x)树的“最小节点”连边，则直径最小为(min(x+z+2,x+y+1,y+z+1)=y+z+1)，(x,z)与(y)同理。
建树后求树的直径即可。
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int fst[N],nxt[2*N],v[2*N],cnt;
int siz[N],rt[N],dp[N],t[N],pos;
int d[N],qwq[N],qaq[N],tot,ans;
//siz[i]:编号为i树的"最小深度",rt[i]:编号为i树的"最小节点",dp[i]:i号节点为根时它所在树的最大深度
//t[i]:编号为i结点所在树的编号,qwq/qaq:记录答案的建边
void add(int a,int b)
{
v[++cnt]=b;
nxt[cnt]=fst[a]; fst[a]=cnt;
}
void dfs1(int x)
{
t[x]=pos;
for(int i=fst[x];i;i=nxt[i])
{
int y=v[i];
if(!t[y]) dfs1(y);
}
}
int dfs2(int x,int fa)
{
int sum=0;
for(int i=fst[x];i;i=nxt[i])
{
int y=v[i];
if(y==fa) continue;
sum=max(sum,dfs2(y,x));
}
return sum+1;
}
void dfs3(int x,int fa)
{
for(int i=fst[x];i;i=nxt[i])
{
int y=v[i];
if(y==fa) continue;
dfs3(y,x);
ans=max(ans,d[x]+d[y]+1);
d[x]=max(d[x],d[y]+1);
}
}
int main()
{
int n,m,x,y;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
add(x,y); add(y,x);
}
//计算t数组
for(int i=1;i<=n;i++)
if(!t[i]) {pos++; dfs1(i);}
//计算dp数组
for(int i=1;i<=n;i++) dp[i]=dfs2(i,0)-1;
//计算siz数组
memset(siz,0x3f,sizeof(siz));
for(int i=1;i<=n;i++)
if(dp[i]<siz[t[i]]) {siz[t[i]]=dp[i]; rt[t[i]]=i;}
//求出最小深度最大树的最小节点
int maxi=-1,maxn;
for(int i=1;i<=pos;i++)
if(siz[i]>maxi) {maxi=siz[i]; maxn=i;}
//记录答案+建边
for(int i=1;i<=pos;i++)
{
if(i!=maxn)
{
qwq[++tot]=rt[maxn]; qaq[tot]=rt[i];
add(rt[maxn],rt[i]); add(rt[i],rt[maxn]);
}
}
//求树的直径
dfs3(1,0);
printf("%d
",ans);
for(int i=1;i<=tot;i++) printf("%d %d
",qwq[i],qaq[i]);
return 0;
}