python/TangDou/Topic/HuanGenDp/POJ3585.cpp

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
const int N = 2e5 + 10, M = N << 1;

int n, du[N];

// 链式前向星
int e[M], h[N], idx, w[M], ne[M];
void add(int a, int b, int c = 0) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

int f[N], g[N];

// 以1号点为根， 由子推父，先递归，再统计
void dfs1(int u, int fa) {
    for (int i = h[u]; ~i; i = ne[i]) {
        int v = e[i];
        if (v == fa) continue;
        dfs1(v, u);
        if (du[v] == 1)
            f[u] += w[i];
        // 如果v是叶子,u->v的边权可以加到f[u]中
        // 代表着u的最大消化能力,比如样例中的4号节点，它连接着3和5两个节点，边权分别是5,10
        // 所以它的最大消化能力=5+10=15
        else // 如下对方节点不是叶子，比如1号节点，需要取f(1)=min(w[u][v],f(4))
             // 当然，别忘了1也可能有其它的子节点，需要要使用f[1]+=
             // f[u]:表示向底向上统计来的1号节点的消化能力
            f[u] += min(f[v], w[i]);
    }
}
// 自顶向下，由父推子，先计算，后递归
void dfs2(int u, int fa) {
    for (int i = h[u]; ~i; i = ne[i]) {
        int v = e[i];
        if (v == fa) continue;
        if (du[u] == 1) // 如果u是叶子 ，那么w[v][u]=w[i]是可以火力全开的
            g[v] = f[v] + w[i];
        else // 如果u不是叶子
            g[v] = f[v] + min(g[u] - min(f[v], w[i]), w[i]);
        // 先计算再递归
        dfs2(v, u);
    }
}

int main() {
    // 加快读入
    ios::sync_with_stdio(false), cin.tie(0);
    int T;
    cin >> T;
    while (T--) {
        // 初始化链式前向星
        memset(h, -1, sizeof h);
        idx = 0;
        memset(du, 0, sizeof du);
        memset(f, 0, sizeof f);
        memset(g, 0, sizeof g);

        cin >> n;

        int a, b, c;
        for (int i = 1; i < n; i++) { // 树，n-1条无向边
            cin >> a >> b >> c;
            add(a, b, c), add(b, a, c);
            du[a]++, du[b]++; // 记录入度,无向图就不谈入度和出度了
        }
        // 第一遍dfs
        dfs1(1, 0);
        g[1] = f[1];

        // 第二遍dfs
        dfs2(1, 0);

        int ans = 0;
        for (int i = 1; i <= n; i++) ans = max(ans, g[i]);
        cout << ans << endl;
    }
    return 0;
}