补题链接：Here
一个树形水系，有 (n) 个结点，根结点称为源点，叶子结点称为汇点，每条边都有水量限制$C(x,y) (()x,y$ 为这条边的两个端点)，源点单位时间流出的水量称为整个水系的流量，求以哪一个结点作为源点整个水系的流量最大。
首先得理解到这是一道“不定根”的树形DP问题，这类题目的特点是，给定一个树形结构，需要以每个结点为根进行一系列统计。我们一般通过两次扫描来求解此类问题：（也即：二次扫描与换根法）
- 第一次扫描时任选一个点为根，在“有根树”上执行一次“树形DP”，也就是在回溯时发生的、自底向上的状态转移。
- 第二次扫描，从刚才选出的根出发，对整棵树执行一次DFS，在每次递归前进行自上而下的推导，计算出“换根”之后的解。
首先，我们任选一个结点 root ，然后树形DP一下，求出 (D_{root}) 数组（ (D[i]) 表示在以 (i) 为根的子树中流量的最大值)。然后设 (f_x) 表示以 (x) 为源点，流向整个水系的最大流量，则显然 (f_{root} = D_{root}) 假设 (f_x) 已经求出，考虑其子结点 (y) ，则 (f[y]) 包含两部分：
- 从 (y) 流向以 (y) 为根的子树的流量，已经计算出来。
- 从 (y) 沿着到父节点 (x) 的河道，进而流向水系中其他部分的流量。
由题意可知，从 (x) 流向 (y) 的流量为 (min(D_y,c_{x,y})) ，所以从 (x) 流向除 (y) 以外其他部分的流量分量是其两者之差：(f_x - min(D_y,c_{x,y})) 于是，把 (y) 作为源点，先从流到 (x)，再流向其他部分的流量就是吧这个“差值”再与 (c_{x,y}) 取较小值后的结果
[if(deg[x] > 1) o f[y] = D[y] + min(f[x] - min(D[y],c[x][y]) - c[x][y])\
if(deg[x] == 1) o f[y] = D[y] + c[x][y]
]
这是一个由下而上的递推方程，所以我们可以通过一次DFS来完成
AC 代码
// Murabito-B 21/04/26
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const int N = 2e5 + 5;
using pii = pair<int, int>;
vector<pii> g[N];
int dp[N], d[N], f[N];
void dfs(int u, int fa) {
for (int i = 0; i < g[u].size(); ++i) {
int v = g[u][i].fi, w = g[u][i].se;
if (v == fa) continue;
dfs(v, u);
if (d[v] == 1) dp[u] += w;
else
dp[u] += min(dp[v], w);
}
}
void dfs1(int u, int fa) {
f[u] = dp[u];
for (int i = 0; i < g[u].size(); ++i) {
int v = g[u][i].fi, w = g[u][i].se;
if (v == fa) continue;
if (d[v] == 1) {
dp[u] -= w;
dp[v] += min(dp[u], w);
} else {
dp[u] -= min(w, dp[v]);
dp[v] += min(w, dp[u]);
}
dfs1(v, u);
}
}
void solve() {
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
g[i].clear();
d[i] = dp[i] = f[i] = 0;
}
for (int i = 1; i < n; ++i) {
int u, v, w;
cin >> u >> v >> w;
g[u].push_back({v, w});
g[v].push_back({u, w});
d[u]++, d[v]++;
}
dfs(1, -1);
// f[1] = dp[1];
dfs1(1, -1);
int ans = 0;
for (int i = 1; i <= n; ++i) ans = max(ans, f[i]);
cout << ans << '
';
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int _;
for (cin >> _; _--;) solve();
return 0;
}