题意

给你一个森林(若干棵树),向其中加边，使得最后形成一棵树，要求最后形成的树的直径最小，输出这棵树的直径和所加的边

分析

每加一条边，都可以将两棵树合并成一棵树，总共有t = n - m棵树

也就是说我们需要在这t棵树里面，分别选一个点，将他们连接起来，使得最后形成一棵直径最小的树

这个点的性质是，以这个点为根节点转化为有根树的画，树的高度一定是最小的（与重心类似，最长链最短可以保证合并后直径最短）

稍加分析可以知道，这个点一定是直径的中点（直径两端到该点的距离相差不超过1）

所以我们维护一棵树，可以维护以下几点性质：

1. 树的直径dig

2. 树的直径的中点序号center

3. 树的直径两端离center较远的点(相同则任意)site

这样合并A,B两颗树后，新的树

dig = max ( A.dig , B.dig , ceil(A.dig/2) + ceil(B.dig/2) )

遍历这棵树，仍然求得新的center和site

那么以怎样的顺序合并呢？

通过上面dig的转移式可以看出，如果两棵树site到center的距离不相等，则形成的新树的直径不变（等于大的一棵树），否则直径变大

所以我们希望最小化这个影响（不变大）

考虑最大的三棵树$A.dig ≥ B.dig ≥ C.dig$

第一次将最大的两颗树合并起来，得到的一棵新树D

如果$A.dig == B.dig$

则$D.dig > C.dig$则之后D和C合并直径不会变

否则$A.dig > C.dig$之后D和C合并直径不会变

可证得每次合并最大的两棵树

如此操作下去直到合成一棵树,得到的直径一定最小

其实不用优先队列维护，只需要排序后，每次取未合并的最大的树，与当前维护的树合并即可（类似prim算法合并的思路）

代码

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 
  4 int n,m;
  5 vector<int>edge[1005];
  6 int color[1005];
  7 void rs(int pre,int now,int co) {
  8     color[now] = co;
  9     for(auto it = edge[now].begin();it!=edge[now].end();it++) {
 10     if(*it == pre) continue;
 11     rs(now,*it,co);
 12     }
 13     return;
 14 }
 15 struct Tree{
 16     int dig,center,site;
 17     bool operator < (const Tree& o) const {
 18     return dig < o.dig;
 19     }
 20 }tree;
 21 priority_queue<Tree>pq;
 22 int far,X,Y,id;
 23 void dfs(int pre,int now,int dis){
 24     if(dis>far) {
 25     far = dis;id =now;
 26     }
 27     for(auto it = edge[now].begin();it!=edge[now].end();it++) {
 28     if(*it == pre) continue;
 29     dfs(now,*it,dis+1);
 30     }
 31 }
 32 stack<int>st;
 33 int flag;
 34 vector<pair<int,int> >ans;
 35 void dfs2(int pre,int now,int aim){
 36     if(now == aim) {
 37     tree.site = now;
 38     for(int i=1;i<(far+1)/2;i++){ st.pop();}
 39     tree.center = st.top();
 40     tree.dig = far;
 41     pq.push(tree);
 42     flag = 1;
 43     while(!st.empty())st.pop();
 44     return;
 45     }
 46     st.push(now);
 47     for(auto it = edge[now].begin();it!=edge[now].end();it++) {
 48     if(*it == pre) continue;
 49     dfs2(now,*it,aim);
 50     if(flag) return;
 51     }
 52     st.pop();
 53 }
 54 int main() {
 55     ios::sync_with_stdio(false);
 56     cin>>n>>m;
 57     int x,y;
 58     for(int i=1;i<=m;i++) {
 59     cin>>x>>y;
 60     edge[x].push_back(y);
 61     edge[y].push_back(x);
 62     }
 63     int co = 0;
 64     for(int i=1;i<=n;i++) {
 65     if(color[i]==0) {
 66         rs(0,i,++co);
 67         far=0;id = i;
 68         dfs(0,i,0);
 69         X = id;
 70         far=0;id = X;
 71         dfs(0,X,0);
 72         Y = id;
 73         if(X == Y) {
 74         tree.site = X;
 75         tree.center = X;
 76         tree.dig = 0;
 77         pq.push(tree);
 78         }
 79         else {
 80         flag =0;
 81         dfs2(0,X,Y);
 82         }
 83     }
 84     }
 85     while(pq.size()>1) {
 86     Tree a = pq.top();pq.pop();
 87     Tree b = pq.top();pq.pop();
 88     far = max(a.dig,((a.dig+1)/2) + ((b.dig+1)/2) +1);
 89     far = max(b.dig,far);
 90     edge[a.center].push_back(b.center);
 91     edge[b.center].push_back(a.center);
 92     flag =  0;
 93     dfs2(0,a.site,b.site);
 94     ans.push_back(make_pair(a.center,b.center));
 95     }
 96     tree = pq.top();
 97     cout<<tree.dig<<endl;
 98     
 99     for(auto it = ans.begin();it!=ans.end();it++) {
100     cout<<it->first<<" "<<it->second<<endl;
101     }
102     
103 
104 }