时间复杂度$O(n^2)$的做法可以通过本题。但我们可以继续优化到$O(n)$。本文将分别介绍这两种做法。

$O(n^2)$做法

我们把树上距离最大的一对点，称为树的直径。

枚举断掉哪条边，设断掉的边为$(u,v)$。那么树就被分成了包含$u$的连通块和包含$v$的连通块，这两部分。再连边时，新边的两个端点，一定分别位于两个连通块里，记这两个端点为$(u',v')$。新树的直径，可能有三种情况：

1. $u$所在连通块的直径。
2. $v$所在连通块的直径。
3. 【$u$所在连通块里，与$u'$距离最大的点的距离】+【边$(u,v)$的长度】+【$v$所在连通块里，与$v'$距离最大的点的距离】。

前两个情况，长度是已经确定的，与我们如何选择$u',v'$无关。可以先将前两个情况的长度求出来。第3个情况，发现$u'$, $v'$的选择是互不影响的，可以分别求最小值。于是问题转化为，有一棵树（也就是$u$或$v$所在的连通块），请你求一个点$x$，使得树上所有点到$x$的最大距离最小。

先随便选一个点作为根（在具体实现时，不妨就选$u$和$v$）。求出“树上”所有点到根的最大距离。然后换根，这样就能求出以每个点为根的情况，然后取最小的即可。为了换根，我们要先求出每个点子树内，到它距离最大和次大的点，求次大的，是为了避免换根时，要换的那个子树恰好就是最大的。

这样，就在$O(n)$的时间里求出了断掉这条边时，新树的最小直径。对每条边的情况取最小值，就是答案了。

时间复杂度$O(n^2)$。

$O(n)$做法

需要一些观察。

观察一：我们要断掉的边，一定在原树的直径上。

否则不会使直径变小。

观察二：根据观察一，$u$, $v$两个连通块里，一定分别有一个原直径的端点。那么，$u$, $v$两个连通块的直径，其中的一端，一定是原直径的端点。

否则原直径就不是最长的了。不符合直径的定义。

观察三：前面我们用换根法解决的问题：

有一棵树（也就是$u$或$v$所在的连通块），请你求一个点$x$，使得树上所有点到$x$的最大距离最小。

这个点$x$，一定就是树的直径的中点（是带权意义上的中点）。​

根据观察一，我们可以按顺序枚举直径上的每条边。此时，两边的连通块，会新多出一部分节点，或者新减少一部分节点。对于减少的情况，我们反着走一遍，它就也变成了新增。

每次遍历这些“新增”的部分，然后利用观察二，更新直径。发现新增部分的总和是$O(n)$的。这样，就能在总共$O(n)$的时间里，求出$u,v$各自所在连通块的直径。

再根据观察三，我们要找的$x$不需要用换根法了。由于每次新增一些部分后，连通块的直径长度是单调不降的，那么“直径中点”也是“单调”的，向前枚举即可。

时间复杂度$O(n)$。

参考代码

因为博主是鸽子，所以只写了$O(n^2)$的代码。

//problem:P3761
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mk make_pair
#define lob lower_bound
#define upb upper_bound
#define fi first
#define se second
#define SZ(x) ((int)(x).size())

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;

const int MAXN=5000;
const int INF=1e9;
int n,cnt;
struct EdgeAndSize{
	int u,v,w,sz_u,sz_v;
	EdgeAndSize(int _u,int _v,int _w,int _su,int _sv){
		u=_u;v=_v;w=_w;sz_u=_su;sz_v=_sv;
	}
	EdgeAndSize(){}
}e[MAXN+5];

struct EDGE{int nxt,to,w;}edge[MAXN*2+5];
int head[MAXN+5],tot;
inline void add_edge(int u,int v,int w){
	edge[++tot].nxt=head[u],edge[tot].to=v,edge[tot].w=w,head[u]=tot;
}

int sz[MAXN+5];
void dfs1(int u,int fa){
	sz[u]=1;
	for(int i=head[u];i;i=edge[i].nxt){
		int v=edge[i].to;
		if(v==fa)continue;
		dfs1(v,u);
		e[++cnt]=EdgeAndSize(u,v,edge[i].w,n-sz[v],sz[v]);
		sz[u]+=sz[v];
	}
}
int f[MAXN+5],f2[MAXN+5];
void dfs2(int u,int fa){
	f[u]=f2[u]=0;
	for(int i=head[u];i;i=edge[i].nxt){
		int v=edge[i].to;
		if(v==fa)continue;
		dfs2(v,u);
		int val=f[v]+edge[i].w;
		if(val>f[u]){
			f2[u]=f[u];
			f[u]=val;
		}
		else if(val>f2[u]){
			f2[u]=val;
		}
	}
}
void dfs3(int u,int fa,int& mn,int& mx){
	mn=min(mn,f[u]);
	mx=max(mx,f[u]);
	for(int i=head[u];i;i=edge[i].nxt){
		int v=edge[i].to;
		if(v==fa)continue;
		//换根
		int t=f[u];
		if(f[v]+edge[i].w==f[u])t=f2[u];
		int val=t+edge[i].w;
		if(val>f[v]){
			f2[v]=f[v];
			f[v]=val;
		}
		else if(val>f2[v]){
			f2[v]=val;
		}
		dfs3(v,u,mn,mx);
	}
}
int main() {
	cin>>n;
	for(int i=1;i<=n-1;++i){
		int u,v,w;cin>>u>>v>>w;
		add_edge(u,v,w);add_edge(v,u,w);
	}
	dfs1(1,0);
	assert(cnt==n-1);
	int ans=INF;
	for(int i=1;i<=n-1;++i){
		dfs2(e[i].u,e[i].v);
		int min_u=INF,max_u=0;
		dfs3(e[i].u,e[i].v,min_u,max_u);
		
		dfs2(e[i].v,e[i].u);
		int min_v=INF,max_v=0;
		dfs3(e[i].v,e[i].u,min_v,max_v);
		
		ans=min(ans,max(min_u+min_v+e[i].w,max(max_u,max_v)));
	}
	cout<<ans<<endl;
	return 0;
}

D56 树的直径 两次DFS+双指针 P3761 [TJOI2017] 城市

// 树的直径 树形DP 暴力 O(n^2)
#include<bits/stdc++.h>
using namespace std;

const int N=5010;
int h[N],idx=1;
struct edge{int to,w,ne;} e[N<<1];
void add(int x,int y,int w){
  e[++idx]={y,w,h[x]}; h[x]=idx;
}
int n,d1[N],d2[N],son[N],up[N],mxd,ans=1e9;
bool col[N<<1];

void dfs1(int x,int fa){ //树形DP 求直径
  for(int i=h[x];i;i=e[i].ne){
    int y=e[i].to,w=e[i].w;
    if(y!=fa&&!col[i]){
      dfs1(y,x);
      if(d1[x]<d1[y]+w) d2[x]=d1[x],d1[x]=d1[y]+w,son[x]=y; //x下挂的最长链、次长链，x最长链的儿子
      else if(d2[x]<d1[y]+w) d2[x]=d1[y]+w;
    }
  }
  mxd=max(mxd,d1[x]+d2[x]); //直径=最长链+次长链
}
void dfs2(int x,int fa){ //类似树的中心求法 求半径
  for(int i=h[x];i;i=e[i].ne){
    int y=e[i].to,w=e[i].w;
    if(y!=fa&&!col[i]){
      if(son[x]==y) up[y]=max(up[x],d2[x])+w; //y上方的最长距离=max(x上方的最长距离+w(x,y)，x的次长链+w(x,y))
      else up[y]=max(up[x],d1[x])+w; //y上方的最长距离=x的最长链+w(x,y)
      dfs2(y,x);
    }
  }
  mxd=min(mxd,max(up[x],d1[x])); //半径=min{max{x上方的最长距离,x的最长链}}
}
int main(){
  scanf("%d",&n);
  for(int i=1,x,y,w;i<n;i++){
    scanf("%d%d%d",&x,&y,&w);
    add(x,y,w);add(y,x,w);
  }
  for(int i=2,zjx,zjy,bjx,bjy;i<=idx;i+=2){ //枚举边
    memset(d1,0,sizeof d1);
    memset(d2,0,sizeof d2);
    memset(up,0,sizeof up);
    memset(son,0,sizeof son);        
    int x=e[i].to,y=e[i^1].to,w=e[i].w;
    col[i]=col[i^1]=1; //断边染色
    mxd=0; dfs1(x,0); zjx=mxd;
    mxd=0; dfs1(y,0); zjy=mxd;
    mxd=1e9; dfs2(x,0); bjx=mxd;
    mxd=1e9; dfs2(y,0); bjy=mxd;
    ans=min(ans,max(max(zjx,zjy),bjx+bjy+w)); //最大直径的最小值
    col[i]=col[i^1]=0; //断边去色
  }
  printf("%d",ans);
}

#include<bits/stdc++.h>
using namespace std;
const int N=5005,INF=0x3f3f3f3f;
struct edge{int x, y, c, pre;} a[2*N]; int alen, last[N];
void ins(int x, int y, int c) {alen++; a[alen]=edge{x, y, c, last[x]}; last[x]=alen;}
bool v[N]; int n, dis, rad, d1[N], d2[N], dy[N];
void getd(int x)
{
	v[x]=1; 
	for(int k=last[x]; k; k=a[k].pre)
	{
		int y=a[k].y; if(v[y]==1) continue;  
		getd(y);
		if(d1[x]<d1[y]+a[k].c) {d2[x]=d1[x]; d1[x]=d1[y]+a[k].c; dy[x]=y;}
		else if(d2[x]<d1[y]+a[k].c)          d2[x]=d1[y]+a[k].c;
	}
	dis=max(dis, d1[x]+d2[x]);
}
void getr(int x, int fr)
{
	rad=min(rad, max(fr, d1[x])); v[x]=0;
	for(int k=last[x]; k; k=a[k].pre)
	{
		int y=a[k].y; if(v[y]==0) continue;  
		if(y!=dy[x]) getr(y, max(d1[x]+a[k].c, fr+a[k].c));
		else         getr(y, max(d2[x]+a[k].c, fr+a[k].c));
	}
}
int main()
{
	int n;scanf("%d", &n); 
	alen=0; memset(last, 0, sizeof(last));
	for(int i=1,x, y, c; i<n; i++)
	{
		scanf("%d%d%d", &x, &y, &c);
		ins(x, y, c); ins(y, x, c);
	}
	int ans=INF;
	for(int i=1; i<=alen; i+=2)
	{
		for(int j=1; j<=n; j++) d1[j]=d2[j]=v[j]=dy[j]=0;
		int rad1, rad2, dis1, dis2;
		v[a[i].y]=1; 
		dis=0; getd(a[i].x); dis1=dis;
		dis=0; getd(a[i].y); dis2=dis;
		v[a[i].y]=0; 
		rad=INF; getr(a[i].x, 0); rad1=rad;
		rad=INF; getr(a[i].y, 0); rad2=rad;
		ans=min( ans, max({dis1, dis2, rad1+rad2+a[i].c}) );
	}
	printf("%d\n", ans);
	return 0;
}