算法

(换根)

首先随便选取一个点作为根节点，我们可以dfs遍历一遍得到这个点为根时的答案，接下来我们考虑枚举这个根节点的儿子成为新的根节点后的答案。首先暴力扫一遍是不可取的，复杂度难以承受，那我们怎么计算答案呢？
假设根节点为rt，儿子结点为u，孙子结点为v，我们先计算rt所有相邻结点的最大流量和，然后枚举哪个儿子成为新根，然后老的根就成为了新根的儿子（相当于孙子），计算新根和所有儿子（老孙子）的流量和就行了。
针对代码中可能有看不懂的，pair就相当于两个变量的结构体，first是第一个元素，second是第二个，auto是C++ 11新特性，相当于遍历数组。
原博客在： https://blog.csdn.net/qq_41785863/article/details/98541880 欢迎大家指出错误

C++ 代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
vector<pair<int, ll> > e[maxn];
ll dp[maxn]; //i为根节点时的最大流量和
ll ans[maxn];
int n;

void dfs1(int u, int fa) //计算
{
    ll tmp = 0;
    for(auto x : e[u])
    {
        int v = x.first;
        if(v == fa) continue;
        //dp[v] = x.second;
        if(e[v].size() == 1) //叶子结点
            dp[v] = e[v][0].second;
        dfs1(v, u);
        dp[u] += min(dp[v], x.second);
    }
}

void dfs(int u, int fa) //遍历整棵树
{
    ll tmp = 0; //tmp是u所有儿子的和
    for(auto x : e[u])
    {
        if(e[u].size() == 1)
            tmp = x.second;
        else
        {
            int v = x.first;
            tmp += min(dp[v], x.second);
        }
    }
    for(auto x : e[u]) //枚举哪个儿子当根
    {
        int v = x.first; //v是儿子
        if(v == fa) continue;
        ll rt = dp[u], son = dp[v];
        dp[u] = tmp; //父亲变成新根的儿子
        if(e[u].size() > 1) //不是叶子结点
           dp[u] = dp[u] - min(dp[v], x.second);
        dp[v] = 0;
        for(auto m : e[v]) //枚举新根的儿子
        {
            dp[v] += min(dp[m.first], m.second);
        }
        ans[v] = dp[v]; //记录答案
        dfs(v, u);
        //dp[u] = rt, dp[v] = son; //回溯
    }
}

int main()
{
    //freopen("input.txt", "r", stdin);
    int t;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        for(int i = 0; i <= n; ++i)
            e[i].clear(), dp[i] = 0;
        for(int i = 1; i < n; ++i)
        {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            e[u].push_back(make_pair(v, w));
            e[v].push_back(make_pair(u, w));
        }
        dfs1(1, 0); //先计算1为根结点的情况
        ans[1] = dp[1];
        dfs(1, 0);
        /*for(int i = 1; i <= n; ++i)
            cout << dp[i] << " ";
        cout << endl;*/
        ll res = -1e9;
        for(int i = 1; i <= n; ++i)
            res = max(res, ans[i]);
        printf("%lld\n", res);
    }
    return 0;
}


/*
1
7
1 2 1
1 3 13
3 4 10
3 5 5
4 6 4
4 7 3
*/