积蓄程度

AcWing-287-积蓄程度

分析

见《进阶指南》第292页。

实现

#include <iostream>
#include <cstring>
using namespace std;

const int N = 200010, M = 2 * N;
struct edge {
    int to, next, w;
};
edge e[M];
int idx, head[N];
int n, deg[N], f[N], g[N];

void add_edge (int u, int v, int w) {
    e[idx].w = w;
    e[idx].to = v;
    e[idx].next = head[u];
    head[u] = idx ++;
}
void dfs1 (int cur, int fa) {
    for (int i = head[cur]; i != -1; i = e[i].next) {
        int to = e[i].to, w = e[i].w;
        if (to == fa) continue;
        dfs1(to, cur);
        if (deg[to] == 1) {
            f[cur] += w;
        } else {
            f[cur] += min(w, f[to]);
        }
    }
}
void dfs2 (int cur, int fa) {
    for (int i = head[cur]; i != -1; i = e[i].next) {
        int to = e[i].to, w = e[i].w;
        if (to == fa) continue;
        if (deg[cur] == 1) {
            g[to] = f[to] + w;
        } else {
            g[to] = f[to] + min(w, g[cur] - min(w, f[to]));
        }
        dfs2(to, cur);
    }
}

int main () {
    int T;
    scanf("%d", &T);
    while (T --) {
        // ---------- 重置 ----------
        idx = 0;
        memset(head, -1, sizeof(head));
        memset(deg, 0, sizeof(deg));
        memset(f, 0, sizeof(f));

        scanf("%d", &n);
        for (int i = 1, u, v, w; i <= n - 1; ++ i) {
            scanf("%d%d%d", &u, &v, &w);
            add_edge(u, v, w);
            add_edge(v, u, w);
            ++ deg[u];
            ++ deg[v];
        }

        dfs1(1, -1);
        g[1] = f[1];
        dfs2(1, -1);
        int res = 0;
        for (int i = 1; i <= n; ++ i)
            res = max(res, g[i]);
        printf("%d\n", res);
    }
    return 0;
}