树型动态规划 - NOI提高级教程

📖 算法原理：后序遍历与树上递推

树型动态规划是在树状结构上进行的 DP。由于树具有天然的递归子结构，我们通常采用 后序遍历 (Post-order DFS)：先深度搜索所有子节点，在回溯归纳时再将子树的信息汇集给父节点进行决策。

📐 “没有上司的舞会”状态转移方程

每个节点代表一个职员，其有特定的快乐值 fun[u]。任何职员都不能与其直接上司同时参加舞会。求舞会最大快乐值之和。

我们用 f[u][1] 表示职员 $u$ 参加舞会时，$u$ 及其子树能获得的最大快乐；f[u][0] 表示 $u$ 不参加舞会时的最大快乐：

情况 1：u 亲自参加 (f[u][1])：
一旦 $u$ 参加，所有直属下属 $v$ 均不能参加：
$f[u][1] = fun[u] + \sum_{v \in child(u)} f[v][0]$
情况 2：u 放弃参加 (f[u][0])：
若 $u$ 放弃，其直属下属 $v$ 均可以参加，也可以放弃，我们选择每人最优的决策累加：
$f[u][0] = \sum_{v \in child(u)} \max(f[v][0], f[v][1])$

演示速度：

点击"开始演示"或"单步执行"观察后序 DFS 递归，以及状态自下向上反馈给父节点并决策的过程。

🌲 树型 DP 状态波流汇聚图 (The Company Party Visualizer)

已计算节点：0 / 7

舞会最大快乐值：0

void dfs(int u) {
    f[u][0] = 0;
    f[u][1] = fun[u]; // 亲自参会初始快乐
    
    for (int v : child[u]) {
        dfs(v); // 递归先求解子树
        
        // 状态转移归纳
        f[u][0] += max(f[v][0], f[v][1]); // 放弃上司，下属选最优
        f[u][1] += f[v][0]; // 亲自出席，下属必须缺席
    }
}

📋 树上状态回溯汇集日志