跨越树形动态规划的高维映射技术

核心逻辑与数学原理

树形动态规划（Tree DP）的基础模型通常只关注子树内的状态收敛（如自底向上）。然而，考场上的高难度题目往往会引入全源拓扑交互或局部连通块限制。

要跨越树形 DP 的最高门槛，必须透彻掌握以下两个核心高维映射技术：

多状态交叉网络（Multi-state Interleaving）：当题目限制不再是简单的“选或不选”（如没有上司的舞会），而是存在多级传导链（例如：一个节点被保安覆盖，可以是它自己装了监控，也可以是它的父亲装了，或者是它的某个儿子装了）。这种多向依存关系会导致传统的二维状态彻底瘫痪。我们必须通过定义全完备状态集，在父子节点之间建立跨维度的网格交织。
树上上下文信息解耦（Re-rooting Context Isolation）：在 16.3 节的换根法中，我们接触了全源信息的转移。但在更复杂的场景中（如求树上海明距离次大值、或者转移方程中包含无法逆运算的算子时），简单的“全局 - 子树 = 外部”的差分逻辑会失效。此时，必须在第一次扫描时，对父节点的所有直接子节点维护前缀最值与后缀最值网格，从而在换根向下推进时，能够无损地剥离出除当前子节点外的“其他所有兄弟子树的聚合贡献”。

状态设计与算法推导

以经典的“树的最小支配集（Minimum Dominating Set）”为例（即：选出最少的节点涂黑，使得树中所有节点要么自身被涂黑，要么与至少一个黑点相邻）。

1. 全完备状态空间设计

对于任意节点 $u$，要让以 $u$ 为根的子树全部被合法覆盖，且满足拓扑传导，其自身的状态有且仅有以下 3 种完全完备的物理语义：

$f[u][0]$：节点 $u$ 自身被涂黑。此时其子节点 $v$ 是否被覆盖已经无所谓，状态可以任意切换。
$f[u][1]$：节点 $u$ 自身不涂黑，但被其某个直接子节点 $v$ 涂黑覆盖。这意味着 $u$ 的所有子节点中，至少有一个必须选择状态 0。
$f[u][2]$：节点 $u$ 自身不涂黑，且没有被子节点覆盖，只能等待其父节点未来被涂黑来覆盖它。这意味着 $u$ 的所有子节点自身都必须已经被合法覆盖，且它们没有义务向上贡献（即子节点不能是状态 2）。

2. 状态转移方程的几何交织

对于父节点 $u$ 和它的子节点集合 $ ext{son}(u)$：

状态 0（自身涂黑）：由于 $u$ 已经独立，子节点 $v$ 可以在三种状态中任意挑选最小成本。

$$f[u][0] = 1 + \sum_{v \in \text{son}(u)} \min(f[v][0], f[v][1], f[v][2])$$

状态 2（等待父亲覆盖）：由于 $u$ 没涂黑且儿子不帮它，所有子节点 $v$ 必须自己站稳脚跟。由于 $u$ 没涂黑，子节点 $v$ 绝不能是状态 2（否则 $v$ 会处于未覆盖的真空期）。

$$f[u][2] = \sum_{v \in \text{son}(u)} \min(f[v][0], f[v][1])$$

状态 1（靠儿子覆盖，致命推导点）： $u$ 没涂黑，所有子节点 $v$ 首先至少要在状态 0 和状态 1 中选一个：$\sum \min(f[v][0], f[v][1])$。但这里隐藏着一个核心漏洞：万一所有的子节点在求 $\min$ 时，全都倒向了状态 1 怎么办？ 如果全选了状态 1，说明没有一个儿子自身涂黑，那父节点 $u$ 就会陷入无人覆盖的非法状态。因此，我们必须强制挑出一个儿子 $v'$ 变成状态 0。为了让总代价增幅最小，我们需要枚举哪个儿子改为状态 0 带来的“补差价”最小：

$$f[u][1] = \sum_{v \in \text{son}(u)} \min(f[v][0], f[v][1]) + \Delta_{min}$$

其中 $\Delta_{min} = \min_{v \in \text{son}(u)} \{ f[v][0] - \min(f[v][0], f[v][1]) \}$。如果原本的组合中就已经有儿子选了状态 0，则 $\Delta_{min} = 0$。

C++ 标准源码（NOIP风格）

以下源码为树的最小支配集的标准工业级实现，完美演示多状态网络交互在考场上的精细控制。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 100005;
const int INF = 0x3f3f3f3f;

vector<int> edge[MAXN];
int f[MAXN][3]; 
// f[u][0]: u黑
// f[u][1]: u白,靠儿子黑
// f[u][2]: u白,靠父亲黑

void dfs(int u, int fa) {
    f[u][0] = 1; // 自身涂黑，初始代价为 1
    f[u][2] = 0; // 靠父亲覆盖，当前局部初始化代价为 0

    int sum_1_0 = 0;
    int min_gap = INF;
    bool has_zero = false; // 记录是否有儿子自发选择了状态 0

    // 判断是否为叶子节点的哨兵标志
    bool is_leaf = true;

    for (int v : edge[u]) {
        if (v == fa) continue;
        is_leaf = false;

        dfs(v, u); // 拓扑沉底

        // 1. 更新 f[u][0]
        f[u][0] += min({f[v][0], f[v][1], f[v][2]});

        // 2. 更新 f[u][2]
        f[u][2] += min(f[v][0], f[v][1]);

        // 3. 为 f[u][1] 收集基准累加和并计算差价
        int best_sub = min(f[v][0], f[v][1]);
        sum_1_0 += best_sub;

        if (f[v][0] <= f[v][1]) {
            has_zero = true;
        }
        min_gap = min(min_gap, f[v][0] - best_sub);
    }

    // 边界特判：若是叶子节点，触底赋予物理极值
    if (is_leaf) {
        f[u][0] = 1;
        f[u][1] = INF; // 叶子没有儿子，不可能靠儿子覆盖，赋予无穷大
        f[u][2] = 0;   // 等待父亲覆盖是合法的
        return;
    }

    // 4. 精细组合 f[u][1] 状态
    if (has_zero) {
        f[u][1] = sum_1_0; // 已有儿子选了 0，不需要强制补差价
    } else {
        f[u][1] = sum_1_0 + min_gap; // 强制拉一个代价增幅最小的儿子变成状态 0
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    if (!(cin >> n)) return 0;

    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }

    dfs(1, 0);

    // 根节点没有父亲，所以全局最优解只能在状态 0 和状态 1 中产生
    cout << min(f[1][0], f[1][1]) << "\n";

    return 0;
}

NOIP 实战避坑指南

1. 忽略叶子节点的特殊边际状态赋值

现象：选手在多状态树形 DP 中，容易忽略叶子节点的特殊性。例如在上面的模型中，如果不给叶子节点特判 f[u][1] = INF，叶子节点由于没有进入子节点循环，f[u][1] 会保持默认值 0。这就产生了“叶子节点靠不存在的儿子覆盖了自己且代价为 0”的荒谬状态，向上转移时会严重污染整棵树。
规避手段：在 DFS 内部枚举子树循环结束后，必须针对 is_leaf 状态进行物理语义的二次审视，强制纠正不符合现实的边界值。

2. 差价法 (`min_gap`) 未处理 `INF` 导致数据溢出

现象：在计算 $f[u][1]$ 的补差价时，如果某个子树的 f[v][0] 本身就是 INF（由于某种限制导致非法），直接执行 f[v][0] - best_sub 会导致 INF - best_sub 依然是一个极大值。如果不加甄别地加进总和里，会触发整型下溢出（变为负数）。
规避手段：在进行大范围状态转移或差价计算时，若前驱状态含有 INF，应当通过 if 语句强行拦截，不参与差分运算。

经典 NOIP/洛谷真题

1. 洛谷 P2899 [USACO08JAN] Cell Phone Network G

题意描述：给定一棵 $N$ 个节点的树，要在一些节点上建立基站。一个基站可以覆盖它自身以及所有与之直接相连的相邻节点。求最少需要建立多少个基站才能覆盖整棵树。$N \le 10000$。
问题本质与解题思路：标准的树的最小支配集问题。
核心思路：完全等价于上述推导的 3 状态模型。利用二维数组 f[u][0/1/2] 进行状态拓扑交织，在单次 DFS 内完成计算。

2. 洛谷 P2458 [SDOI2006] 保安站岗

题意描述：一棵树上有 $N$ 个小镇，在每个小镇设立保安站需要花费一定的经费 $W_i$。每个小镇设立的保安站只能保护与其直接相连的街道和小镇。求经费最少的设计方案。
问题本质与解题思路：带点权特化的树的最小支配集。
核心思路：与上题唯一的区别在于，状态 0 的基础代价不再是统一的 1，而是每个节点各自的独立点权 W[u]。
状态修正：

$$f[u][0] = W[u] + \sum \min(f[v][0], f[v][1], f[v][2])$$

其余靠儿子覆盖、靠父亲覆盖的决策流与差价逻辑完全一致。本题将离散计数无损升维映射到连续的费用网格上，是省选及 NOIP 提高组的高频经典题。