【题意】
给出一棵带边权的树，删掉一条边，再加上一条相同权值的边，使得在保持新图仍是一棵树的情况下，最远点对距离最小，求出这个距离。
【题解】
枚举删掉哪条边，然后原图变成2棵树。
之后的加边肯定是加在2棵树重心的两端，dp一下即可。
再在所有情况取最小值。注意别只考虑通过新边的路径，还有2棵树内部直径要考虑。
【代码】
1 #include <iostream> 2 #include <cstdio> 3 using namespace std; 4 const int N=5005; 5 const int inf=2e9; 6 int l,s,sum,now,ans,n,a[N],b[N],c[N],dp[N][2],last[N],nxt[N<<1],to[N<<1],va[N<<1]; 7 bool vis[N]; 8 void add(int x,int y,int z) 9 { 10 nxt[++l]=last[x];last[x]=l;to[l]=y;va[l]=z; 11 nxt[++l]=last[y];last[y]=l;to[l]=x;va[l]=z; 12 } 13 void modif(int u,int s) 14 { 15 if (s>dp[u][0]) dp[u][1]=dp[u][0],dp[u][0]=s; 16 else if (s>dp[u][1]) dp[u][1]=s; 17 } 18 void dfs(int u,int f) 19 { 20 vis[u]=1; 21 for (int x=last[u];x;x=nxt[x]) 22 { 23 int v=to[x]; 24 if (v==f) continue; 25 dfs(v,u); 26 modif(u,dp[v][0]+va[x]); 27 } 28 } 29 void dfs2(int u,int f) 30 { 31 now=max(now,dp[u][0]+dp[u][1]); 32 s=min(s,max(dp[u][0],dp[u][1])); 33 for (int x=last[u];x;x=nxt[x]) 34 { 35 int v=to[x]; 36 if (v==f) continue; 37 if (dp[u][0]==dp[v][0]+va[x]) modif(v,dp[u][1]+va[x]); 38 else modif(v,dp[u][0]+va[x]); 39 dfs2(v,u); 40 } 41 } 42 void clr() 43 { 44 l=sum=now=0; 45 for (int i=1;i<=n;++i) last[i]=dp[i][0]=dp[i][1]=vis[i]=0; 46 } 47 int main() 48 { 49 scanf("%d",&n); 50 if (n==1) return puts("0"),0; 51 for (int i=1;i<n;++i) 52 scanf("%d%d%d",&a[i],&b[i],&c[i]); 53 ans=inf; 54 for (int i=1;i<n;++i) 55 { 56 for (int j=1;j<i;++j) add(a[j],b[j],c[j]); 57 for (int j=i+1;j<n;++j) add(a[j],b[j],c[j]); 58 for (int k=1;k<=n;++k) 59 if (!vis[k]) 60 { 61 dfs(k,0); 62 s=inf; 63 dfs2(k,0); 64 sum+=s; 65 } 66 ans=min(max(now,sum+c[i]),ans); 67 clr(); 68 } 69 printf("%d ",ans); 70 return 0; 71 }