代码实现

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+5,inf=1<<29;
typedef long long ll;
typedef pair<int,int> pii;
#define mk(a,b) make_pair(a,b)
struct Edge{ int v,next,w;}edge[maxn] ; 
int tot,head[maxn],f[maxn],d[maxn],v[maxn],deg[maxn] ;
void add(int u,int v,int w) {
    edge[++tot].next=head[u]; edge[tot].w=w;
    edge[tot].v=v; head[u]=tot;
}
void dp(int x) {
    v[x]=1; d[x]=0;
    for(int i=head[x];i;i=edge[i].next) {
        int y=edge[i].v;
        if(v[y]) continue;
        dp(y);
        if(deg[y]==1) d[x]+=edge[i].w;
        else d[x]+=min(edge[i].w,d[y]);
    }
}
void dfs(int x) {
    v[x]=1;
    for(int i=head[x];i;i=edge[i].next) {
        int y=edge[i].v;
        if(v[y]) continue;
        if(deg[x]==1) f[y]=d[y]+edge[i].w;
        else f[y]=d[y]+min(f[x]-min(d[y],edge[i].w),edge[i].w) ;
        dfs(y) ;
    }
}
void init() {
    memset(deg,0,sizeof(deg) ); //标记 
    tot=0; //图 
    memset(head,0,sizeof (head) ) ;
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
    int t; cin>>t;
    while(t--) {
        int n; cin>>n;
        init() ;
        for(int i=1;i<n;i++) {
            int a,b,c;
            cin>>a>>b>>c;
            add(a,b,c),add(b,a,c) ;
            deg[a]++,deg[b]++;
        }
        memset(v,0,sizeof(v) ) ; 
        dp(1); //求root到每个子树的最大值 
        memset(v,0,sizeof(v) ) ;
        f[1]=d[1] ; //d表示从i出发向其子树流出的最大量 
        dfs(1); //换根 
        //print
        int ans=0;
        for(int i=1;i<=n;i++) ans=max(ans,f[i]);
        cout<<ans<<endl; 
    }
    return 0;
}