常规树形dp

Wanderer

2026-04-22 10:00:15

发布于：广东

9阅读

0回复

0点赞

本篇截取自OI Wiki

以下面这道题为例，介绍一下树形 DP 的一般过程．

洛谷 P1352 没有上司的舞会
某大学有 𝑛 个职员，编号为 1 ∼𝑁.
他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司．现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 $a_{i}$ ，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了．
所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数．

我们设 𝑓(𝑖,0/1) 代表以 𝑖 为根的子树的最优解（第二维的值为 0 代表 𝑖 不参加舞会的情况，1 代表 𝑖 参加舞会的情况）．
对于每个状态，都存在两种决策（其中下面的 𝑥 都是 𝑖 的儿子）：
上司不参加舞会时，下属可以参加，也可以不参加，此时有

$𝑓(𝑖,0) = ∑max {(𝑓(𝑥,1),𝑓(𝑥,0))}$

上司参加舞会时，下属都不会参加，此时有

$𝑓(𝑖,1) =∑𝑓(𝑥,0) +ai$

我们可以通过 DFS，在返回上一层时更新当前结点的最优解．

#include <algorithm>
#include <iostream>
using namespace std;

struct edge {
  int v, next;
} e[6005];

int head[6005], n, cnt, f[6005][2], ans, is_h[6005], vis[6005];

void addedge(int u, int v) {  // 建图
  e[++cnt].v = v;
  e[cnt].next = head[u];
  head[u] = cnt;
}

void calc(int k) {
  vis[k] = 1;
  for (int i = head[k]; i; i = e[i].next) {  // 枚举该结点的每个子结点
    if (vis[e[i].v]) continue;
    calc(e[i].v);
    f[k][1] += f[e[i].v][0];
    f[k][0] += max(f[e[i].v][0], f[e[i].v][1]);  // 转移方程
  }
  return;
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> f[i][1];
  for (int i = 1; i < n; i++) {
    int l, k;
    cin >> l >> k;
    is_h[l] = 1;
    addedge(k, l);
  }
  for (int i = 1; i <= n; i++)
    if (!is_h[i]) {  // 从根结点开始DFS
      calc(i);
      cout << max(f[i][1], f[i][0]);
      return 0;
    }
}