CSP Wiki By Yundou树形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了，有没有感受到先遍历子树，遍历完之后将子树的值传给父亲这样的动态规划过程呢？
树的平衡点
给你一个有个点的树，求树的平衡点和删除平衡点后最大子树的节点数。所谓平衡点，指的是树中的一个点，删掉该点，使剩下的若干个连通块中，最大的连通块的块大小最少。
要解决这个问题，我们首先还是先确定状态，现在的问题还很简单，一般就是题目问什么我们就设什么，所以我们先设为删除号点后最大连通块的块大小。然后我们沿用上一题的设为以为根的子树大小，那么很简单就有，其中是的子节点。这是因为，删除号点后，我们剩下的连通块要么是的子树，要么是的父亲所在的连通块。
通俗的来讲，即删除某个节点后，它的儿子就成了独立的连通块，那么最大连通块就是 max(x 的所有儿子连通块最大的 size，n - f[x])
所以我们只需要先沿用第一题的方法先算出每个点的子树大小，再DFS一遍算出每个点的，其值最小的点就是我们树的平衡点。
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;
}没有上司的舞会 （树的最大独立集）
某大学有 个职员，编号为 。他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 ，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。
我们把题意抽象一下，没有职员会和上司一同参会，也就是说在这棵树上不存在任何一条边使得连接的两个点都来参会，换句话说这道题其实要我们求的是 树的最大权值的独立集。
我们设 代表以 为根的子树的最优解（第二维的值为 0 代表 不参加舞会的情况，1 代表 参加舞会的情况）。
对于每个状态，都存在两种决策（其中下面的 都是 的儿子）：
- 上司不参加舞会时，下属可以参加，也可以不参加，此时有 ；
- 上司参加舞会时，下属都不会参加，此时有 。
我们可以通过 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 遍历子树的所有最优解，然后向上传递给子树的父节点来转移，最终根节点的值即为所求的最优解。