solution

经典的的方式。

转化一下题意就是:选一个根，使得所有叶子节点到该节点路径上最小边权之和最大。

先考虑的做法

用表示以1为根时i这棵子树内的答案。那么就有。

所以枚举一下根，然后每次这样dfs一遍，就可以在时间内解决问题了。

考虑优化该算法

我们只要在以1为根做一遍上面自下而上的dp之后，在做一遍自上而下的dp就可以转移出以任何一个点为根时的答案。
转移方程就是:，表示在自下而上的dp过程中，v对于u的贡献。

code

/*
* @Author: wxyww
* @Date: 2020-04-12 20:30:52
* @Last Modified time: 2020-04-12 20:43:48
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N = 200010;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
struct node {
    int v,nxt;ll w;
}e[N << 1];
int head[N],ejs;
void add(int u,int v,int w) {
    e[++ejs].v = v;e[ejs].w = w;e[ejs].nxt = head[u];head[u] = ejs;
}
ll f[N];
void dfs1(int u,int fa) {
    for(int i = head[u];i;i = e[i].nxt) {
        int v = e[i].v;
        if(v == fa) continue;
        dfs1(v,u);
        f[u] += min(e[i].w,f[v]);
    }
    if(!f[u]) f[u] = 1e14;
}
void dfs2(int u,int fa) {
    for(int i = head[u];i;i = e[i].nxt) {
        int v = e[i].v;
        if(v == fa) continue;
        f[v] += min(e[i].w,f[u] - min(f[v],e[i].w));
        dfs2(v,u);
    }
}
int main() {
    int T = read();

    while(T--) {
        int n = read();
        memset(head,0,sizeof(head));
        ejs = 0;
        for(int i = 1;i < n;++i) {
            int u = read(),v = read(),w = read();
            add(u,v,w);add(v,u,w);
        }
        memset(f,0,sizeof(f));
        dfs1(1,0);
        dfs2(1,0);
        ll ans = 0;
        for(int i = 1;i <= n;++i) {
            if(f[i] > 1e13) continue;
            ans = max(ans,f[i]);
            // printf("%lld ",f[i]);
        }
        // puts("");
        cout<<ans<<endl;
    }

    return 0;
}