435 树形DP 积蓄程度【动态规划】

```C++

#include <iostream>

#include <cstring>

#include <algorithm>

using namespace std;

const int N = 200010, INF = 0x3f3f3f3f;

int h[N], to[N * 2], w[N * 2], ne[N * 2], tot; //邻接表

int d[N];   //d[u]记录从u点向下流出的最大流量

int up[N];  //up[u]记录从u点向上流出的最大流量

int deg[N];  //deg[i]记录点i的度数

void add(int a, int b, int c) {

to[++tot] = b, w[tot] = c, ne[tot] = h[a], h[a] = tot;

}

int dfs_d(int u, int fa) { //从叶点开始向上递推u点的下流量

for (int i = h[u]; i; i = ne[i]) {

int v = to[i];

if (v == fa) continue;

int s = dfs_d(v, u); //返回v点的下流量

d[u] += min(w[i], s); //累加u点的下流量

}

if (deg[u] == 1) return w[h[u]]; //若u是叶

return d[u];         //返回u点的下流量

}

void dfs_up(int u, int fa) { //从根点开始向下递推v点的上流量

for (int i = h[u]; i; i = ne[i]) {

int v = to[i];

if (v == fa) continue;

if (deg[u] == 1) up[v] = w[i];

// else if (deg[v] == 1) up[v] = min(w[i], d[u] - w[i] );

else up[v] = min( d[u] - min(d[v], w[i]) + up[u], w[i]);

dfs_up(v, u);

}

}

int main() {

int t, n;

scanf("%d", &t);

while (t--) {

scanf("%d", &n);

tot = 0;

memset(h, 0, sizeof h);

memset(d, 0, sizeof d);

memset(up, 0, sizeof up);

memset(deg, 0, sizeof deg);

for (int i = 1; i < n; i++) {

int a, b, c;

scanf("%d%d%d", &a, &b, &c);

add(a, b, c), add(b, a, c);

deg[a]++, deg[b]++;

}

dfs_d(1, -1); //向上递推下流量

up[1] = 0;  //根的上流量为0

dfs_up(1, -1); //向下递推上流量

int ans = 0;

for (int i = 1; i <= n; i++) ans = max(ans, up[i] + d[i]);

printf("%d\n", ans);

}

return 0;

}

```

注释部分是代码 else if (deg[v] == 1)是雍余逻辑