一道很好的树形dp问题
P10974 Accumulation Degree
题目简述
给定一棵树，每条边有一个正容量。度为 1 的节点称为终端节点（叶子节点）。
定义：
- A(x)：从节点 x 出发，能够流向其他所有终端节点的最大流量之和。
- 累积度：所有节点中最大的 A(x) 值。
任务是求给定树的累积度。
核心思想
对于任意节点 u，它向叶子节点输送的流量可以分为两个方向：
- 向子树方向（不经过父节点）
- 向父节点方向（经过父节点）
因此：
text
A(u) = d[u] + up[u]
其中：
d[u]：u 向子树方向（子节点方向）能输送的最大流量up[u]：u 通过父节点方向能获得的最大流量
算法步骤
第一步：第一次 DFS（自底向上）
计算每个节点的 d[u]（向下流量）。
递推公式：
对于 u 的每个子节点 v：
-
如果 v 是叶子节点（
deg[v] == 1）：text
d[u] += w(u, v) -
如果 v 不是叶子节点：
text
d[u] += min(d[v], w(u, v))
为什么取 min？
从 u 流向 v 方向的流量，受两个因素限制：
- 边
(u, v)的容量 - v 向下输送的能力
d[v]
所以取两者最小值。
叶子节点处理：
叶子节点没有子节点，所以在 DFS 时跳过递归，直接累加边容量。
第二步：第二次 DFS（换根，自顶向下）
利用父节点的累积度，计算子节点的累积度。
核心公式：
已知父节点 u 的累积度 f[u]，要计算子节点 v 的累积度 f[v]：
text
flow_to_v = min(d[v], w(u, v)) // u 流向 v 的流量
other = f[u] - flow_to_v // u 除 v 方向外的其他流量
up_from_parent = min(other, w(u, v)) // v 通过父节点方向获得的流量
f[v] = d[v] + up_from_parent
特殊情况：
当 u 是叶子节点时（deg[u] == 1），u 没有其他方向可以提供流量，所以：
text
f[v] = d[v] + w(u, v)
根节点：
根节点没有父节点，所以：
text
f[root] = d[root]
第三步：求答案
遍历所有节点，取 f[i] 的最大值。
注意：当 n == 1 时，没有叶子节点（度为1的节点不存在），此时累积度为 0。
时间复杂度
- 两次 DFS 各遍历所有节点一次：O(n)
- 总时间复杂度：O(n)
- 空间复杂度：O(n)
代码实现
#include <bits/stdc++.h>
using namespace std;const int N = 2e5 + 10;int T, n;
vector<pair<int, int>> g[N];
int d[N]; // d[u]：向下流量
int f[N]; // f[u]：累积度 A(u)
int deg[N]; // 度数// 第一次DFS：计算向下流量 d[u]
void dfs1(int u, int fa) {d[u] = 0;for (auto [v, w] : g[u]) {if (v == fa) continue;if (deg[v] == 1) {// v是叶子节点，不递归d[u] += w;} else {// v不是叶子节点，先递归再计算dfs1(v, u);d[u] += min(d[v], w);}}
}// 第二次DFS：换根计算累积度 f[u]
void dfs2(int u, int fa) {for (auto [v, w] : g[u]) {if (v == fa) continue;if (deg[u] == 1) {// u是叶子节点，只能提供w的流量f[v] = d[v] + w;} else {int flow_to_v = min(d[v], w);int other = f[u] - flow_to_v;f[v] = d[v] + min(other, w);}dfs2(v, u);}
}int main() {ios::sync_with_stdio(false);cin.tie(0);cin >> T;while (T--) {cin >> n;// 初始化for (int i = 1; i <= n; i++) {g[i].clear();d[i] = f[i] = deg[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});deg[u]++;deg[v]++;}// 特殊情况：只有一个节点if (n == 1) {cout << 0 << '\n';continue;}int root = 1;// 第一次DFSdfs1(root, -1);// 根节点的累积度 = 向下流量f[root] = d[root];// 第二次DFS（换根）dfs2(root, -1);// 求最大值int ans = 0;for (int i = 1; i <= n; i++) {ans = max(ans, f[i]);}cout << ans << '\n';}return 0;
}