在树上设计动态规划算法时，一般按照节点的深度从深到浅，（或者说子树从小到大）的顺序作为 DP 的”阶段“。DP 的状态表示中，第一维通常是节点编号。

求解树形动态规划时，往往采用递归的方式进行。对于每个节点 $x$ ，先递归遍历处理其每个子节点，在回溯时，从 $x$ 的子节点向节点 $x$ 进行状态转移。

没有上司的舞会

问题

Ural大学有 $N$ 名职员，编号为 1~N。他们的关系就像一棵以校长为根的树，父节点就是子节点的直接上司。每个职员有一个快乐指数，用整数 $H_i$ 给出，其中 $1\leq i\leq N$。现在要召开一场周年庆宴会，不过，没有职员愿意和直接上司一起参会。在满足这个条件的前提下，主办方希望邀请一部分职员参会，使得所有参会职员的快乐指数总和最大，求这个最大值。

分析

$F[x][0]$ 表示 $x$ 不参加舞会时，以 $x$ 为根的子树能够获得的最大的快乐值。

$F[x][1]$ 表示 $x$ 参加舞会时，以 $x$ 为根的子树能够获得的最大的快乐值。

$y_1, y_2,…,y_i,…$ 表示 $x$ 的直接下属。

当 $x$ 不参加舞会时。他的下属可以参加也可以不参加舞会。因此得出状态转移方程：
$$
F[x][0] = \sum \limits_{y \in son(x)} max(F[y_i][0], F[y_i][1])；
$$
当 $x$ 参加舞会时，他的直接下属都不参加舞会，因此得到状态转移方程：
$$
F[x][1] = H[x] + \sum \limits_{y\in son(x)}F[y_i][0]；
$$
目标 $ans = max(F[root][1], F[root][0]);$

代码

#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 6006;
int n;
int  h[N];
bool v[N];
int f[N][2];
int root;
vector<int>son[N];  // next[x] 表示x的下属的集合 

void dp(int x) {
    f[x][0] = 0;
    f[x][1] = h[x];
    for (int y: son[x]) {
        dp(y);
        f[x][0] += max(f[y][0], f[y][1]);
        f[x][1] += f[y][0];
    }
}

int main() {
    scanf("%d", &n);
    memset(v, 0, sizeof(v));
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &h[i]);
    }
    for (int i = 1; i <= n-1; ++i) {
        int l, k;
        scanf("%d%d", &l, &k);  // K 是 L的上司
        son[k].push_back(l);
        v[l] = true;  // 表示l有上司；
    }
    for (int i = 1; i <= n; ++i) {
        if (v[i] == false) {
            root = i;
            break;
        }
    }
    dp(root);
    int ans = max(f[root][0], f[root][1]);
    printf("%d\n", ans);
    return 0;
}

动态规划（四）树形DP

Contents

没有上司的舞会