Accumulation Degree（换根dp）

题目：

一棵树，边有流量。让你找一个点u到所有叶子结点路径上流量和最大。

做法：

换根dp。
首先选定一个非叶子结点 $rt$ 为根，一遍 $dfs$ 得到子树 $u$ 到该子树下叶子结点的流量 $flow[u]$ 。 $flow[u] += min(flow[v], w);$ （v是u的儿子结点，w是边的流量）。 $dp[u]$ 表示以 $u$ 为树根点，到所有叶子结点路径上流量和。显然此时 $dp[rt] = flow[rt]$ 我们以此为基础再一遍 $dfs$ 将根换到儿子结点，求得所有 $dp$ 值。
考虑根从 $u$ 换到 $v$ 的影响。
首先子树 $v$ 向下的流量加上去，然后截断 $u$ 向 $v$ 的流量，并加上从 $v$ 到 $u$ 的流量： $dp[v] = flow[v]+min(w, dp[u]-min(flow[v], w));$
最后 $ans=max(dp[i]);$
PS:代码中为了处理方便，叶子结点的流量flow被设成了边的流量，在换根dp时需要减回来。
PPS:感谢评论区指出错误：不能默认用1为根，因为1可能是叶子结点换根时会少算通向1的流量。所以我们要特判 $n=1$ 和 $n=2$ 的情况，当 $n>2$ 时，树上必定存在非叶子结点 $rt$ ，从 $rt$ 开始 $dfs$ 就不会出现问题了。

代码：

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << endl
using namespace std;
typedef long long ll;
const int N = 2e5 + 7;
const int inf = 0x3f3f3f3f;
int n;
ll flow[N], dp[N];
vector<pair<int,int> > g[N];
void dfs(int u, int p){
    if (g[u].size() == 1 && u != p) return;
    flow[u] = 0;
    for (int i = 0; i < g[u].size(); ++i){
        int v = g[u][i].first, w = g[u][i].second;
        if (v == p) continue;
        flow[v] = w;
        dfs(v, u);
        flow[u] += min(flow[v], 1ll*w);
    }
}
void dfs1(int u, int p){
    for (int i = 0; i < g[u].size(); ++i){
        int v = g[u][i].first, w = g[u][i].second;
        if (v == p) continue;
        dp[v] = flow[v]+min(1ll*w, dp[u]-min(flow[v], 1ll*w));
        if (g[v].size() == 1) dp[v] -= flow[v];
        dfs1(v, u);
    }
}
int main(void){
    IOS;
    int T; cin >> T;
    while (T--){
        cin >> n;
        for (int i = 1; i <= n; ++i) g[i].clear();
        for (int i = 0; i < n-1; ++i){
            int u, v, w; cin >> u >> v >> w;
            g[u].push_back(make_pair(v, w));
            g[v].push_back(make_pair(u, w));
        }
        if (n == 1){
            cout << 0 << endl; continue;
        }else if (n == 2){
            cout << g[1][0].second << endl; continue;
        }
        int rt;
        for (rt = 1; rt <= n && g[rt].size() == 1; ++rt);
        dfs(rt, rt);
        dp[rt] = flow[rt];
        dfs1(rt, rt);
        ll ans = 0;
        for (int i = 1; i <= n; ++i){
            ans = max(ans, dp[i]);
        }
        cout << ans << endl;
    }    return 0;
}