好啦首先我们不要被数据范围吓到，常数适宜的情况下3s时限O(n^2)可以信仰过5000，毕竟只是相较1000翻了25倍，如果我们的算法可以在100-120ms内通过1000，就可以凭借信仰过掉这道题

本题题解

其实我们发现这道题是可以暴力枚举删那一条边的，这首先有了一个O(N)的复杂度 ，我们接下来要用另一个O(N)处理最远点对的问题

那么删去这条边之后，整棵树将被分为两个联通块

那么此时的最长路有三种来源，

1.两个端点都在联通块1中

2.两个端点都在联通块2中

3.两个端点一个在联通块1，另一个在联通块2

对于1和2我们求一个树上直径即可，对于问题3呢?

我们发现，如果连接了u，v，那么最长路就是 u到联通块1任意一点的最长距离+val+v到联通块2的任意一点最长距离。如果我们适当的选取u和v，使得这两个点的到自己联通块的最长距离最小。那么就是最优的决策了。

也就是说我们要求树上的半径？

树上半径求法

首先我们先做一边树形dp，对于每一个子树，求出经过它的最长链和次长链 然后直径就是枚举每一个点，它的最长链+次长链的最大值

那么半径呢？我们考虑一件事，就是距离它最远的那个点，在它的子树内还是子树外。

如果在子树内，距离就是第一遍dfs求出的最长链，如果在子树外的话，我们在树上在做第二遍dfs，这个dfs额外传一个from参数，from表示这个子树之外的最长链

那么这个最长链from有两个来源

1.它父亲的from+它和父亲的距离

2.它父亲的其他子树中的最长链+他和父亲的距离

对于情况二，如果他就是父亲的所有孩子中的最长链，那么我们的情况2要取次长链，如果不是取最长链就可以了。

然后枚举每个点，半径就是min(max(dp[i],from[i]))了

然后只需做4遍一半的dfs即可，代码也是非常的好写

(小技巧:dfs的时候直接把另一个点打上访问标记即可只dfs一半)

上代码~

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=5010;const int INF=0x3f3f3f3f;
struct data{int v;int nxt;int val;}edge[2*N];
int alist[N];int cnt;int n;
inline void add(int u,int v,int val)
{edge[++cnt].v=v;edge[cnt].nxt=alist[u];alist[u]=cnt;edge[cnt].val=val;}
int dp[N];int mv[N];int nxdp[N];bool book[N];int rad=INF;int dis;int res=INF;
void getd(int x)//求直径 
{
    book[x]=true;int nxt=alist[x];
    while(nxt)
    {
        int v=edge[nxt].v;int val=edge[nxt].val;
        if(!book[v])
        {
            getd(v);int va=dp[v]+val;//最长链和次长链 
            if(va>dp[x]){nxdp[x]=dp[x];dp[x]=va;mv[x]=v;}
            else if(va>nxdp[x]){nxdp[x]=va;}
        }nxt=edge[nxt].nxt;
    }dis=max(dis,dp[x]+nxdp[x]);//更新直径 
}
void getr(int x,int fr)
{
    rad=min(rad,max(fr,dp[x]));//更新半径 
    book[x]=false;int nxt=alist[x];
    while(nxt)
    {
        int v=edge[nxt].v;int val=edge[nxt].val;
        if(book[v])//更新fr，记得特判自己就是最长链的情况 
        {
            if(v==mv[x]){getr(v,max(nxdp[x]+val,fr+val));}
            else {getr(v,max(dp[x]+val,fr+val));}
        }nxt=edge[nxt].nxt;
    }
}//清空dp的函数 
inline void clear(){for(int i=1;i<=n;i++){dp[i]=mv[i]=nxdp[i]=book[i]=0;}rad=INF;dis=0;}
int u[N];int v[N];int val[N];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<n;i++)//读进来 
    {
        scanf("%d%d%d",&u[i],&v[i],&val[i]);
        add(u[i],v[i],val[i]);add(v[i],u[i],val[i]);
    }
    for(int i=1;i<n;i++)//枚举边 
    {
        int d1;int d2;int r1;int r2;
        book[v[i]]=1;getd(u[i]);d1=dis;//求直径 
        dis=0;getd(v[i]);d2=dis;//求半径 
        book[v[i]]=0;getr(u[i],0);r1=rad;//求直径 
        rad=INF;getr(v[i],0);r2=rad;//求半径 
        res=min(res,max(max(d1,d2),r1+r2+val[i]));//更新答案 
        clear();//不要忘记清空 
    }
    printf("%d",res);return 0;//拜拜程序~ 
}