$ \color{green} {solution : }$

我们可以暴力枚举断边，然后 $ O(n) $ 的跑一次换根 $ dp $，然后复杂度是 $ O(n * n) $ 的

#include 
    
     using namespace std;const int maxn = 100010;template 
     
       inline void G(T &x) {    x = 0; char o; bool f = false;    for ( ; !isdigit(o = getchar()); ) {        if( o == '-') {            f = true;        }    }    for ( ; isdigit(o); o = getchar()) {        x = (x << 1) + (x << 3) + (o & 15);    }    if( f) {        x = ~x + 1;    }}template 
      
        inline bool check_Max(T &x, const T &y) {    return x < y ? x = y, false : true;}template 
       
         inline bool check_Min(T &x, const T &y) {    return x > y ? x = y, false : true;}struct Edge {    int v, w; Edge *to;    Edge ( int v, int w, Edge *to) : v(v), w(w), to(to) {}    Edge () {}}*head[maxn], pool[maxn<<1], *pis = pool;int di[maxn], ndi[maxn];inline void dfs1(int u, int pre, int &Mx) {    di[u] = ndi[u] = 0;    for ( Edge *now = head[u]; now; now = now->to) if( now->v ^ pre) {        dfs1(now->v, u, Mx);            check_Max(ndi[u], di[now->v] + now->w);         if(ndi[u] > di[u]) {            swap(ndi[u], di[u]);        }    }    check_Max(Mx, ndi[u] + di[u]);}inline void dfs2(int u, int pre, int &Mx) {    check_Min(Mx, di[u]);    for ( Edge *now = head[u]; now; now = now->to) if( now->v ^ pre) {        if( di[u] == di[now->v] + now->w) {            check_Max(ndi[now->v], ndi[u] + now->w);            }        else {            check_Max(ndi[now->v], di[u] + now->w);        }        if( ndi[now->v] > di[now->v]) {            swap(di[now->v], ndi[now->v]);        }        dfs2(now->v, u, Mx);    }}int n;struct line {    int l, r, w;}data[maxn];int main() {    G(n);     for ( register int i = 1; i < n; ++ i) {        G(data[i].l); G(data[i].r); G(data[i].w);        int u = data[i].l, v = data[i].r, w = data[i].w;        head[u] = new (pis ++) Edge(v, w, head[u]); head[v] = new (pis ++) Edge(u, w, head[v]);    }    int ans = 0x7fffffff;    for ( register int i = 1; i < n; ++ i) {        int mx1 = 0, mx2 = 0, ret = 0;        dfs1(data[i].l, data[i].r, mx1); dfs1(data[i].r, data[i].l, mx2);        check_Max(ret, mx1); check_Max(ret, mx2);        int mx3 = di[data[i].l], mx4 = di[data[i].r];        dfs2(data[i].l, data[i].r, mx3); dfs2(data[i].r, data[i].l, mx4);        check_Max(ret, mx3 + mx4 + data[i].w);        check_Min(ans, ret);    }    printf("%d\n",ans);    return 0;}
       
      
     
    

---