一道非常类似的题目(link)
试题大意
给你一棵含有$n$个节点的有边权森林，问每次连边将会用$L$的代价，问你若此图通过加边成为树时的最小直径。$n \leq 5\times 10^5$
试题分析
我们可以发现若两棵树要是在合并连接的点一定与树的中心有关。树的中心指对于当$i$为根时，子树上权值和最大的最小。
为什么，应为树的直径的情况只有单独一棵树，两棵树和在一起的，且那时要是合并就是的是树的中心。但其实$CF$那题应该求树的中心也行，因为那是边权都会为$1$.
所以会发现其实应该如果说要把树建完以后会发现是一个菊花树，且根为权重最大的联通块的根。因为若是小的当根的话那么就会多算了一颗树，所以最多只需要算两颗即可。
所以说我们每次处理好中心到叶子节点的最大距离是多少，然后就可以直接去计算答案了。
并且为什么最多只要算到联通块个数$\leq 3$呢，因为刚才说了这是一颗菊花图，所以我们最多有用的其实是两颗子树。
IOI2013
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<climits>
using namespace std;
inline int read(){
int f=,ans=;char c=getchar();
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){ans=ans*+c-'';c=getchar();}
return f*ans;
}
const int N=;
struct node{
int u,v,w,nex;
}x[N<<];
int cnt,head[N],n,m,l;
void add(int u,int v,int w){
x[cnt].u=u,x[cnt].v=v,x[cnt].w=w,x[cnt].nex=head[u],head[u]=cnt++;
}
int dp[N][],dis[N],col,vis[N],son[N];
/*0最长 1 次长*/
void dfs1(int f,int fath){
vis[f]=;
for(int i=head[f];i!=-;i=x[i].nex){
if(x[i].v==fath) continue;
dfs1(x[i].v,f);
if(dp[x[i].v][]+x[i].w>=dp[f][]){dp[f][]=dp[f][];dp[f][]=dp[x[i].v][]+x[i].w,son[f]=x[i].v;}
else if(dp[x[i].v][]+x[i].w>dp[f][]){dp[f][]=dp[x[i].v][]+x[i].w;}
}
return;
}
int ans,k;
void dfs2(int f,int fath,int Dis){
if(Dis>dp[f][]){
dp[f][]=dp[f][];dp[f][]=Dis;son[f]=fath;
}
else if(Dis>dp[f][]){dp[f][]=Dis;}
ans=max(ans,dp[f][]);k=min(k,dp[f][]);
for(int i=head[f];i!=-;i=x[i].nex){
if(x[i].v==fath) continue;
if(son[f]==x[i].v) dfs2(x[i].v,f,dp[f][]+x[i].w);
else dfs2(x[i].v,f,dp[f][]+x[i].w);
}
}
int calc[N];
signed main(){
memset(head,-,sizeof(head));
n=read(),m=read(),l=read();
for(int i=;i<=m;i++){
int u=read()+,v=read()+,w=read();
add(u,v,w),add(v,u,w);
}
for(int i=;i<=n;i++){
if(!vis[i]){
dfs1(i,);
k=INT_MAX;
dfs2(i,,);
calc[++col]=k;
}
}
sort(calc+,calc+col+);
if(col>=) ans=max(ans,calc[col]+calc[col-]+l);
if(col>=) ans=max(ans,calc[col-]+calc[col-]+*l);
printf("%d",ans);
}
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<climits>
using namespace std;
inline int read(){
int f=,ans=;char c=getchar();
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){ans=ans*+c-'';c=getchar();}
return f*ans;
}
const int N=;
struct node{
int u,v,w,nex;
}x[N<<];
int cnt,head[N],n,m,l;
void add(int u,int v,int w){
x[cnt].u=u,x[cnt].v=v,x[cnt].w=w,x[cnt].nex=head[u],head[u]=cnt++;
}
int dp[N][],dis[N],col,vis[N],son[N];
/*0最长 1 次长*/
void dfs1(int f,int fath){
vis[f]=;
for(int i=head[f];i!=-;i=x[i].nex){
if(x[i].v==fath) continue;
dfs1(x[i].v,f);
if(dp[x[i].v][]+x[i].w>=dp[f][]){dp[f][]=dp[f][];dp[f][]=dp[x[i].v][]+x[i].w,son[f]=x[i].v;}
else if(dp[x[i].v][]+x[i].w>dp[f][]){dp[f][]=dp[x[i].v][]+x[i].w;}
}
return;
}
int ans,k,pos;
struct Node{
int pos,calc;
}S[N<<];
void dfs2(int f,int fath,int Dis){
if(Dis>dp[f][]){
dp[f][]=dp[f][];dp[f][]=Dis;son[f]=fath;
}
else if(Dis>dp[f][]){dp[f][]=Dis;}
ans=max(ans,dp[f][]);k=min(k,dp[f][]);
if(dp[f][]==k) pos=f;
for(int i=head[f];i!=-;i=x[i].nex){
if(x[i].v==fath) continue;
if(son[f]==x[i].v) dfs2(x[i].v,f,dp[f][]+x[i].w);
else dfs2(x[i].v,f,dp[f][]+x[i].w);
}
}
bool cmp(Node x1,Node x2){return x1.calc<x2.calc;}
signed main(){
memset(head,-,sizeof(head));
n=read(),m=read(),l=;
for(int i=;i<=m;i++){
int u=read(),v=read(),w=;
add(u,v,w),add(v,u,w);
}
for(int i=;i<=n;i++){
if(!vis[i]){
dfs1(i,);
k=INT_MAX;
dfs2(i,,);
S[++col].calc=k;
S[col].pos=pos;
}
}
sort(S+,S+col+,cmp);
if(col>=) ans=max(ans,S[col].calc+S[col-].calc+l);
if(col>=) ans=max(ans,S[col-].calc+S[col-].calc+*l);
printf("%d\n",ans);
for(int i=col-;i>=;i--) cout<<S[col].pos<<" "<<S[i].pos<<endl;
}
CF