题意

你有一个n个点m条边的森林，编号从0开始，边有边权，你现在要添加若干边权为L的边，满足： 1、最后n个点构成一颗树。 2、这棵树的直径尽量小。 请你求出这个最小的直径是多少。 n<=500000

分析

设d[i]表示i到其所在子树的最远的点的距离。显然每一棵树与其他树相连的必然都是同一个点，且必然是d[i]最小的那个点。然后把每棵树缩成一个点，点权为其最小的d[i]。那么最后一定是构成一个菊花图，且中间那个点必然是点权最大的那个点。 那么我们只要预处理处d[i]，建好图后用两次dfs来求直径即可。

比赛的时候想到了第一个结论，但没想到第二个结论，所以比赛的时候我的做法是动态维护d[i]最小的点：显然d[i]最小的点必然为树的直径的中点，那么只要启发式合并的同时维护直径，再用倍增大法找到其中点即可。 由于我的方法要求lca，不仅多一个log而且还被卡了一波空间2333

代码

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #define N 500005 using namespace std; int n,m,cnt,last[N],mx1[N],mx2[N],num1[N],pts[N],ans,num,L; struct edge{int to,next,len;}e[N*2]; bool vis[N]; void addedge(int u,int v,int len) { e[++cnt].to=v;e[cnt].len=len;e[cnt].next=last[u];last[u]=cnt; e[++cnt].to=u;e[cnt].len=len;e[cnt].next=last[v];last[v]=cnt; } void dp1(int x) { vis[x]=1; for (int i=last[x];i;i=e[i].next) { if (vis[e[i].to]) continue; dp1(e[i].to); int w=mx1[e[i].to]+e[i].len; if (w>mx1[x]) mx2[x]=mx1[x],mx1[x]=w,num1[x]=e[i].to; else if (w>mx2[x]) mx2[x]=w; } } void dp2(int x,int root) { vis[x]=1; if (mx1[x]<mx1[pts[root]]||!pts[root]) pts[root]=x; for (int i=last[x];i;i=e[i].next) { if (vis[e[i].to]) continue; int w=0; if (e[i].to==num1[x]) w=mx2[x]+e[i].len; else w=mx1[x]+e[i].len; if (w>mx1[e[i].to]) mx2[e[i].to]=mx1[e[i].to],mx1[e[i].to]=w,num1[e[i].to]=x; else if (w>mx2[e[i].to]) mx2[e[i].to]=w; dp2(e[i].to,root); } } void dfs(int x,int fa,int len) { if (len>ans) ans=len,num=x; for (int i=last[x];i;i=e[i].next) if (e[i].to!=fa) dfs(e[i].to,x,len+e[i].len); } int main() { scanf("%d%d%d",&n,&m,&L); for (int i=1;i<=m;i++) { int x,y,len; scanf("%d%d%d",&x,&y,&len); addedge(++x,++y,len); } for (int i=1;i<=n;i++) if (!vis[i]) dp1(i); memset(vis,0,sizeof(vis)); for (int i=1;i<=n;i++) if (!vis[i]) dp2(i,i); int x=0; for (int i=1;i<=n;i++) if (pts[i]&&(mx1[pts[i]]>mx1[x]||!x)) x=pts[i]; for (int i=1;i<=n;i++) if (pts[i]&&pts[i]!=x) addedge(x,pts[i],L); dfs(1,0,0); x=num;ans=num=0; dfs(x,0,0); printf("%d",ans); return 0; }