树形DP

在学习树形DP之前，我们先要搞清楚一个问题，什么是树？根据图论课上学到的知识我们知道，连通的无圈图称为树。而树我们可以把它近似第看成一个分形结构，这是说我们的树其实是可以递归定义的，树的每个子树也是一颗完整的树，而这种结构就天然地适合递归。

具体来说，在树形动态规划当中，我们一般先算子树再进行合并，在实现上与树的后序遍历相似，都是先遍历子树，遍历完之后将子树的值传给父亲。简单来说我们动态规划的过程大概就是先递归访问所有子树，再在根上合并。

了解了树形动态规划的基本思想后，做一些经典的树形DP题型。

经典例题

子树大小

给你一棵有个点的树（号点为根节点），求以为根的子树的大小。

这道题作为我们树形动态规划的引例，当然是非常简单的，只要跑一遍即可求出。

具体细节：

设以为根的子树大小，则，其中为子节点。

如果写成伪码，大概长这个样子

void dfs(u){
	if (u 是叶子) f[u] = 1 return
    for (v 是 u 的儿子){
        dfs(v)
        f[u] += f[v]
    }
    f[u] += 1 // 本身
}

这就是最简单的树形DP了，有没有感受到先遍历子树，遍历完之后将子树的值传给父亲这样的动态规划过程呢？

树的平衡点

给你一个有 $n$ 个点的树，求树的平衡点和删除平衡点后最大子树的节点数。所谓平衡点，指的是树中的一个点，删掉该点，使剩下的若干个连通块中，最大的连通块的块大小最少。

要解决这个问题，我们首先还是先确定状态，现在的问题还很简单，一般就是题目问什么我们就设什么，所以我们先设 $F[i]$ 为删除 $i$ 号点后最大连通块的块大小。然后我们沿用上一题的设 $f[i]$ 为以 $i$ 为根的子树大小，那么很简单就有 $F[i] = max(n-f[i],max(f[k]))$ ，其中 $k$ 是 $i$ 的子节点。这是因为，删除 $i$ 号点后，我们剩下的连通块要么是 $i$ 的子树，要么是 $i$ 的父亲所在的连通块。

通俗的来讲，即删除某个节点后，它的儿子就成了独立的连通块，那么最大连通块就是 max(x 的所有儿子连通块最大的 size，n - f[x])

树的平衡点示意图

所以我们只需要先沿用第一题的方法先算出每个点的子树大小，再DFS一遍算出每个点的 $F[i]$ ，其值最小的点就是我们树的平衡点。

 vector<int>e[N];
int ans, idx, f[N];
void dfs(int u, int fa) {
    f[u] = 1;
    int mx = 0;
    for (int v : e[u]) {
        if (v == fa)continue;
        dfs(v, u);
        f[u] += f[v];
        mx = max(mx, f[v]);
    }
    mx = max(mx, n - f[u]);
    if (ans > mx) ans = mx, idx = u;
}

没有上司的舞会（树的最大独立集）

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

我们把题意抽象一下，没有职员会和上司一同参会，也就是说在这棵树上不存在任何一条边使得连接的两个点都来参会，换句话说这道题其实要我们求的是 树的最大权值的独立集。

我们设 $f(i,0/1)$ 代表以 $i$ 为根的子树的最优解（第二维的值为 0 代表 $i$ 不参加舞会的情况，1 代表 $i$ 参加舞会的情况）。

对于每个状态，都存在两种决策（其中下面的 $x$ 都是 $i$ 的儿子）：

上司不参加舞会时，下属可以参加，也可以不参加，此时有 $f(i,0) = \sum\max \{f(x,1),f(x,0)\}$ ；
上司参加舞会时，下属都不会参加，此时有 $f(i,1) = \sum{f(x,0)} + a_i$ 。

我们可以通过 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;
    }
}

通常，树形 DP 状态一般都为当前节点的最优解。先 DFS 遍历子树的所有最优解，然后向上传递给子树的父节点来转移，最终根节点的值即为所求的最优解。

例题：

Status

Problem

树形DP

经典例题

子树大小

树的平衡点

没有上司的舞会 （树的最大独立集）

例题：

On this page

没有上司的舞会（树的最大独立集）