树形DP

“当你有半杯水时，你觉得是有一半空着。还是有一半满了呢？” 鼹鼠问。

“我会感激我拥有一个杯子。” 男孩说。

概述

树形DP，顾名思义，就是在数据结构 “树” 上进行DP。“树” 是有 条边的连通图。通常我们用父子关系来刻画一颗树。

最大独立集

给一无向图，找出一个点集，使得任意两点之间都没有连边，这个点集就是独立集。而点最多的独立集，就是最大独立集。

问题：要从一个无向图里选出一些点，这些点不能相邻，问最多可以选出来多少个点。

思路：设置状态 f[u][0/1] 表示，以 为根节点的子树， 这个点选或者不选，可以选出来的点数。、

初态：对于叶子结点 f[u][0] = 0, f[u][1] = 1

状态转移方程：

$$f[u][0] = \sum_{son} max(f[son][0], f[son][1]) \\ f[u][1] = \sum_{son} f[son][0] + 1$$

void dfs(int u, int f) {
    f[u][0] = 0; f[u][1] = 1;
    for (auto son : e[u])
        if (son != fa) {
            dfs(son, u);
            f[u][0] += max(f[v][0], f[v][1]);
            f[u][1] += f[son][0];
        }
}

最大匹配

匹配：定义一个图 ，匹配是指边集的一个子集 。在 中，没有任意一个节点 ，使得 与 边相连又与 边相连（ ）。

最大匹配：在所有极大匹配中，边集数量最大的那个就是最大匹配，最大匹配可能不唯一。

问题：最大化选的边数，使得所有的点两两配对。

思路：设置状态 f[u][0/1]表示以 为根的子树中，点 是否与其子结点中的一个配对，最多能选多少条边。

状态转移方程：

$$f[u][0] = \sum_{son} f[son][1]$$

如果点 与其子结点中的一个配对，需要枚举这个子结点是谁，其他的子结点，贡献依然为 f[son][1] ，只有该子结点的贡献为 f[son][0] 。对比 f[u][0] ，也就是说要选择一个 f[son][1] - f[son][0] 最小的点与点 相连。

void dfs(int u, int fa) {
    int dlt = 1e9;
    for (auto son :e[u]) {
        f[u][0] += f[son][1];
        dlt = min(dlt, f[son][1] - f[som][0]);
    }
    f[u][1] = f[u][0] - dlt;
}

最小点覆盖

点覆盖的概念定义：对于图 中的一个点覆盖是一个集合 ，使得每一条边至少有一个端点在 中。

最小点覆盖：就是点个数最少的 集合。

思路：设置状态 f[u][0/1] 表示，以 为根的子树中， 这个点选或者不选，选了的点数。

状态转移方程：

$$f[u][1] = \sum_{son} max(f[son][0], f[son][1]) + 1\\ f[u][0] = \sum_{son} f[son][1]$$

void dfs(int um int fa) {
    f[u][0] = 0; f[u][1] = 1;
    for (auto son : e[U])
        if (son != fa) {
            dfs(son, u);
            f[u][1] += max(f[son][0], f[son][1]);
            f[u][0] += f[son][1];
        }
}

练习

洛谷P2986

给一棵树点权为 ，边权为 ，选一个点作为目的地，定义 表示点 到目的地的距离，总路程为 。

问题：选择一个点作为目的地，使得总路程最小。

思路：先随便选择一个点作为根，求出 f[u] 和 sum[u] ，分别表示，以 为根的子树中的点，都走到 的总路程，以及点权和。后面用换根技巧，分别计算到其他点的答案。

#define N 100007
#define ll long long

int tot, hd[N], c[N];

struct edge {int to, w, nxt;} e[N << 1];

inline void add(int u, int v, int w) {
    e[++tot].to = v; e[tot].w = w;
    e[tot].nxt = hd[u]; hd[u] = tot;
}

ll f[N], sum[N];

void dfs(int u, int fa) {
    sum[u] = c[u];
    for (int i = hd[u], v; i; i = e[i].nxt)
        if ((v = e[i].to) != fa) {
            dfs(v, u);
            sum[u] += sum[v];
            f[u] += f[v] + sum[v] * e[i].w;
        }
}

ll ans[N];

void dfs1(int u, int fa) {
    for (int i = hd[u], v; i; i = e[i].nxt)
        if ((v = e[i].to) != fa) {
            ans[v] = ans[u] - sum[v] * e[i].w + (sum[1] - sum[v]) * e[i].w;
            dfs1(v, u);
        }
}

int main() {
    int n = rd();
    for (int i = 1; i <= n; ++i) c[i] = rd();
    for (int i = 1; i < n; ++i) {
        int u = rd(), v = rd(), w = rd();
        add(u, v, w); add(v, u, w);
    }
    dfs(1, 1);
    ans[1] = f[1];
    dfs1(1, 1);
    ll res = 1e18;
    for (int i = 1; i <= n; ++i) res = min(res, ans[i]);
    printf("%lld\n", res);
    return 0;
}