题面：https://www.luogu.com.cn/problem/P3761
一句话题意：给一棵有边权的树，删一条边并加一条等权边，最小化新树的直径。
题解：
考虑先两边DFS求出树的直径。(不会的请自行百度）
那么我们要删的边一定是直径的某一条边。
证明：如果断的不是直径上的边，那么新直径一定\(\geq\)原直径。
既然题目给了\(n^2\)的时限，我们就可以枚举删的是哪一条边。
现在考虑如何连边。
删边后，我们得到了两棵树。那么新的直径可能有三种情况：
A树上的一条链，B树上的一条链，或是A、B合并后经过新边的一条链。
前两个我们可以\(O(n)\)求出。至于第三个，我们类似找树的重心，
----也就是树上离这个点最远距离最小的点。这个可以两边DFS,
第一次记录下每个点的子树距离最大值和次大值，
第二次换根搞一下就好。
时间复杂度O(\(n^2\))
代码：
#include<bits/stdc++.h>
using namespace std;
#define re register int
#define F(x,y,z) for(re x=y;x<=z;x++)
#define FOR(x,y,z) for(re x=y;x>=z;x--)
typedef long long ll;
#define I inline void
#define IN inline int
template<class D>I read(D &res){
res=0;register D g=1;register char ch=getchar();
while(!isdigit(ch)){
if(ch=='-')g=-1;
ch=getchar();
}
while(isdigit(ch)){
res=(res<<3)+(res<<1)+(ch^48);
ch=getchar();
}
res*=g;
}
const int INF=1e9+7;
struct E{
int to,nt,w;
}e[10100];
#define T e[k].to
int n,m,tot,X,Y,W,head[5050],ans,mx[2][5050],d[5050],f[5050];
vector<int>pa;
I add(int x,int y){
e[++tot].to=y;
e[tot].nt=head[x];
head[x]=tot;
e[tot].w=W;
}
I D_1(int x,int fa,int dis){
if(dis>m){m=dis;X=x;}
for(re k=head[x];k!=-1;k=e[k].nt){
if(T==fa||k==W||(k^1)==W)continue;
D_1(T,x,dis+e[k].w);
}
}
I D_2(int x,int fa,int dis){
d[x]=dis;
if(dis>m){m=dis;Y=x;}
for(re k=head[x];k!=-1;k=e[k].nt){
if(T==fa||k==W||(k^1)==W)continue;
D_2(T,x,dis+e[k].w);
}
}
I getpath(int x,int fa){
if(x==Y){m=1;return;}
for(re k=head[x];k!=-1;k=e[k].nt){
if(T==fa||k==W||(k^1)==W)continue;
getpath(T,x);
if(m){
//cout<<"!"<<x<<endl;
pa.emplace_back(k);return;
}
}
}
int mn[2];
I D_3(int x,int fa){
re dis;
for(re k=head[x];k!=-1;k=e[k].nt){
if(T==fa||k==W||(k^1)==W)continue;
D_3(T,x);
dis=mx[0][T]+e[k].w;
if(dis>mx[0][x])mx[1][x]=mx[0][x],mx[0][x]=dis;
else if(dis>mx[1][x])mx[1][x]=dis;
}
}
I D_4(int x,int fa,int dis,int s){
if(dis>mx[0][x])mx[1][x]=mx[0][x],mx[0][x]=dis;
else if(dis>mx[1][x])mx[1][x]=dis;
//cout<<x<<":"<<mx[0][x]<<" "<<mx[1][x]<<endl;
mn[s]=min(mn[s],mx[0][x]);
for(re k=head[x];k!=-1;k=e[k].nt){
if(T==fa||k==W||(k^1)==W)continue;
D_4(T,x,(mx[0][T]+e[k].w==mx[0][x]?mx[1][x]:mx[0][x])+e[k].w,s);
}
}
IN get_diameter(int x,int y,int val){
//cout<<x<<" "<<y<<" "<<val<<" ";
re res=INF;memset(mx,0,sizeof(mx));mn[0]=mn[1]=INF;
D_3(x,0);D_4(x,0,0,0);//cout<<mn<<endl;
m=0;D_1(x,0,0);m=0;D_2(X,0,0);res=d[Y];//cout<<mn[0]<<" "<<d[Y]<<" ";
D_3(y,0);D_4(y,0,0,1);
m=0;D_1(y,0,0);m=0;D_2(X,0,0);res=max(res,max(d[Y],mn[0]+mn[1]+val));
//cout<<mn[1]<<" "<<d[Y]<<" "<<mn[0]+mn[1]+val<<endl;
return res;
}
int main(){
read(n);tot=-1;
memset(head,-1,sizeof(head));
F(i,1,n-1){
read(X);read(Y);read(W);
add(X,Y);add(Y,X);
}
m=0;W=-2;D_1(1,0,0);m=0;D_2(X,0,0);
//cout<<X<<" "<<Y<<endl;
m=0;getpath(X,0);
if(n==1){printf("0");return 0;}
ans=INF;
for(auto p:pa){
//cout<<e[p].to<<" "<<e[p^1].to<<":"<<endl;
W=p;ans=min(ans,get_diameter(e[p].to,e[p^1].to,e[p].w));
//cout<<ans<<endl;
}
printf("%d",ans);
return 0;
}