类似第一篇题解的思路。O(n)，但是WA，只有20分

#include <bits/stdc++.h>
using namespace std;
const int N = 5050;
struct E{
    int ver, nxt, w;
}e[N << 1];int idx = 1;
int h[N];
int n;
void add(int u, int v, int w){
    e[++idx] = (E){v, h[u], w};h[u] = idx;
    e[++idx] = (E){u, h[v], w};h[v] = idx;
}
int dis[N], D[N], fr[N], dc;
int disd[N]; // dis in D
bool ban[N];
int ex[N];
int a, b;
int idz;//中点的idx
void dfs(int u, int fa){
    for(int i = h[u];i;i = e[i].nxt){
        int v = e[i].ver;
        if(v == fa) continue;
        dis[v] = dis[u] + e[i].w;
        fr[v] = u;
        dfs(v, u);
    }
}
void dfs2(int u, int fa){
    for(int i = h[u];i;i = e[i].nxt){
        int v = e[i].ver;
        if(v == fa || ban[v]) continue;
        dfs(v, u);
        ex[u] = max(ex[u], ex[v] + e[i].w);
    }
}
int gd(int x, int y){for(int i = h[x];i;i = e[i].nxt) if(e[i].ver == y) return e[i].w;}
int curd[N], curr[N];
int L[N], R[N], Ld[N], Rd[N];
int main(){
    scanf("%d",&n);
    for(int i = 1, u, v, w;i < n;i++){
        scanf("%d%d%d",&u,&v,&w);
        add(u, v, w);
    }
    dfs(1, 1);
    for(int i = 1;i <= n;i++) if(dis[i] >= dis[a]) a = i;
    dis[a] = 0;fr[a] = -1;
    dfs(a, a);
    for(int i = 1;i <= n;i++) if(dis[i] >= dis[b] && i != a) b = i;
    for(int i = b;i != -1;i = fr[i]){D[++dc] = i;ban[i] = 1;}
    for(int i = 1;i <= dc;i++) dfs2(D[i], D[i]);
    idz = 1;
    L[1] = Ld[1] = curd[1] = 0;
    for(int i = 2;i <= dc;i++){
        disd[i] = disd[i - 1] + gd(D[i], D[i - 1]);
        curd[i] = max(curd[i - 1], disd[i] + ex[D[i]]);
        while(idz < i && max(disd[idz], curd[i] - disd[idz]) > max(disd[idz + 1], curd[i] - disd[idz + 1])) idz++;
        curr[i] = max(disd[idz], curd[i] - disd[idz]);
    } 
   
    for(int i = 2;i <= dc;i++) L[i] = curr[i], Ld[i] = curd[i];
    memset(disd, 0 ,sizeof(disd));
    memset(curd, 0, sizeof(curd));
    memset(curr, 0, sizeof(curd));
    idz = dc;
    R[dc] = curd[dc] = Rd[dc] = 0;
    for(int i = dc - 1;i >= 1;i--){
        disd[i] = disd[i + 1] + gd(D[i], D[i + 1]);
        curd[i] = max(curd[i + 1], disd[i] + ex[D[i]]);
        while(idz > i && max(disd[idz], curd[i] - disd[idz]) > max(disd[idz - 1], curd[i] - disd[idz - 1])) idz--;
        curr[i] = max(disd[idz], curd[i] - disd[idz]);
    }
    ;for(int i = dc - 1;i >= 1;i--) R[i] = curr[i], Rd[i] = curd[i];
    int minn = 1e9 + 100;
    for(int i = 1;i < dc;i++) minn = min(minn, max(max(Ld[i], Rd[i + 1]), L[i] + R[i + 1] + gd(D[i], D[i + 1])));
    printf("%d\n",minn);
}