「poj 3585」 Accumulation Degree(树形DP(二次扫描换根))

poj 3585
题意：找一个点使得，使得从这个点出发作为源点，发出的流量最大，输出这个最大的流量。

本题是一个无根树最优化问题。朴素做法可以是枚举每个点当源点然后树形DP。
考虑随意找一个点DP后，是否其他点可以由这个答案推导出。
设$dp(u)$为以$u$为根子树的最大流量，$f(u)$为整颗树以$u$为根的最大流量。
$dp$的方程式略，具体看进阶指南上的。注意叶节点的讨论
对于$f$的计算，我们知道了$f(v)$的父亲$f(u)$，就能求出$f(v)$的值

$$
f(v)=dp(v)+min(c(x,y), f(u)-min(dp(v), c(x,y)))
$$

注意同样要特判叶节点。

然后最后答案即为$max(f(u))$

知识点：
1、二次扫描换根
2、判是不是叶子最好用度数deg来判

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

int T;

namespace flyinthesky {

    const int MAXN = 200000 + 5;

    struct edge {int v, c, nxt;} ed[MAXN * 2];

    int n, en, hd[MAXN];
    int dp[MAXN], f[MAXN], deg[MAXN];

    void ins(int x, int y, int c) {ed[++en] = (edge){y, c, hd[x]}, hd[x] = en;}

    void dfs1(int u, int fa) {
        dp[u] = 0;
        for (int i = hd[u]; i > 0; i = ed[i].nxt) {
            edge &e = ed[i];
            if (e.v != fa) {
                dfs1(e.v, u);
                if (deg[e.v] == 1) dp[u] += e.c; else dp[u] += min(dp[e.v], e.c); 
            }
        }
    }
    void dfs2(int u, int fa) {
        for (int i = hd[u]; i > 0; i = ed[i].nxt) {
            edge &e = ed[i];
            if (e.v != fa) {
                if (deg[u] == 1) f[e.v] = dp[e.v] + e.c; else f[e.v] = dp[e.v] + min(e.c, f[u] - min(dp[e.v], e.c)); 
                dfs2(e.v, u);
            }
        }
    }

    void clean() {
        en = 0, ms(hd, -1), ms(deg, 0);
    }
    int solve() {
        clean();
        scanf("%d", &n);
        for (int x, y, c, i = 1; i < n; ++i) {
            scanf("%d%d%d", &x, &y, &c);
            ins(x, y, c), ins(y, x, c);
            ++deg[x], ++deg[y];
        }
        dfs1(1, 0);
        f[1] = dp[1], dfs2(1, 0);
        int ans = 0;
        for (int i = 1; i <= n; ++i) ans = max(ans, f[i]);
        printf("%d\n", ans);
        return 0;
    }
}
int main() {
    scanf("%d", &T);
    while (T--) flyinthesky::solve();
    return 0;
}