树形 DP，顾名思义，就是在树上的 DP．

树形 DP 有以下特征：

转移方程一般从当前点的子树转移而来
转换方程的第一维 n 一般表示以 n 为根的子树，怎么怎么样．
一般来说，树的叶子节点是初始状态，根节点是最终状态
一般会综合所有子节点
树形 DP 的实现类似后序遍历．
树形 DP 和线性 DP 有关联，有时候可以相互转化．

树形 DP 一般只有两个顺序：从上往下（不常见）、从下往上，因此，表达式中不能同时存在子节点信息和父节点信息（即无后效性）

典型案例#

树的大小#

给定一棵树，需要统计树中有多少子节点．

这个问题很简单：

状态定义：dp[u] 表示以 u 为根节点的树中有多少子节点．
初始状态：dp[l]=1，其中 l 是叶子节点．
状态转移：dp[u]=sum(dp[v])+1，其中 v 是 u 的子节点．即 dp[u] 为其所有子节点之和再加上本身．
最终状态：dp[r]，r 是根节点．

最大独立集#

题目：P1352 没有上司的舞会

某大学有 $n$ 个职员，编号为 $1\ldots n$ ．

他们之间有从属关系，员工 $k$ 是员工 $l$ 的直接上司，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司．

现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 $r_i$ ，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了．

所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数．

对于 $100\%$ 的数据，保证 $1\leq n \leq 6 \times 10^3$ ， $-128 \leq r_i\leq 127$ ， $1 \leq l, k \leq n$ ，且给出的关系一定是一棵树．

在这里，会用到影响参数化的思想．

状态定义：dp[u][s] 表示以 u 为根节点的树中员工（即员工 u 的间接或直接下属）的最大快乐指数，s 表示员工 u 是（1）否（0）会参加舞会
初始状态：dp[l]=r[l]，其中 l 是叶子节点．
状态转移： $dp[u][0] = max(dp[v][0], dp[v][1], 0)$ ， $dp[u][1] += max(dp[v][0], 0)+r[u]$ ，其中 v 是 u 的子节点．即 dp[u][0] 为其所有子节点去或不去所得的最大值，dp[u][1] 为其所有子节点不去所得的最大值．
最终状态：max(dp[r][0],dp[r][1])，r 是根节点．

标程

#include <bits/stdc++.h>
using namespace std;

const int N = 6e3 + 100;

int n, r[N], dp[N][2], fa[N];
vector<int> e[N];

void dfs(int u) {
    for (int i = 0; i < e[u].size(); i++) {
        int v = e[u][i];
        dfs(v);
        dp[u][0] += max(max(dp[v][0], dp[v][1]), 0);
        dp[u][1] += max(dp[v][0], 0);
    }
    dp[u][1] += r[u];
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> r[i];
    }
    for (int i = 1; i <= n - 1; i++)
    {
        int l, k;
        cin >> l >> k;
        e[k].push_back(l);
        fa[l] = k;
    }
    int root = 1;
    while (1) {
        if (fa[root] == 0) break;
        root = fa[root];
    }
    dfs(root);
    cout << max(dp[root][0], dp[root][1]);
    return 0;
}

cpp

换根 DP#

题目：P3478 STA-Station

给定一个 $n$ 个点的树，请求出一个结点，使得以这个结点为根时，所有结点的深度之和最大．

一个结点的深度之定义为该节点到根的简单路径上边的数量．

对于全部的测试点，保证 $1 \leq n \leq 10^6$ ， $1 \leq u, v \leq n$ ，给出的是一棵树．

想法一：暴力枚举#

尝试以 $O(n)$ 枚举每一个点，然后再通过 dfs 统计一遍答案，总计 $O(n^2)$

想法二#

考虑将根上移带来的贡献．

定义：

sz[t] 表示在 1 为根节点的树中，以 t 为根节点的子树的节点数量．
low[t] 表示在 1 为根节点的树中，以 t 为根的子树中所有节点到节点 t 的距离之和．
dp[t] 表示在 t 为根节点的树中，书中所有节点到节点 t 的距离．

sz[t] 很好求，参考树的大小一节．

第一个 dfs 求 low 时，从下到上，有：

low[u]=sz[u] - 1 +\sum_{u\rightarrow v} low[v]

在上面的式子中：

$sz[u]-1$ 表示边 $u \rightarrow v$ 这条边所做的贡献．
$\sum low[v]$ 表示其子节点的贡献．

边界条件：无需边界条件，所有节点都是自洽的，即使是根节点．

第二个 dfs 求 dp 时，考虑若将根节点从 u 改成 v，v 是 u 的子节点，则有以下变化：

不位于节点 v 下面的节点（不包括 v，共计 $n-sz[v]$ 个节点）每一个到根节点的距离增大 1
位于节点 v 下面的节点（包括 v，共计 $sz[v]$ 个节点）每一个到根节点的距离减少 1

则从上到下，有：

dp[v] = dp[u]+(n-sz[v])-(sz[v])

化简一下，就是：

dp[v]=dp[u]+n-2*sz[v]

考虑边界条件：当 v 是根节点时， $dp[v] = low[v]$

整个题的最终状态为： $max(dp[t]),t\in \mathbb{Z},1\leq t\leq n$

时间复杂度为 $O(n)$

标程：

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 100;

int n, f[N], sz[N], vis[N];
long long dp[N];
int low[N];
vector<int> ee[N], e[N];

void build(int u, int fa = 0) {
    if (vis[u]) return;
    vis[u] = true;
    if (fa != 0) e[fa].push_back(u);
    for (auto it : ee[u]) {
        build(it, u);
    }
}

void dfs_sz(int u) {
    for (auto it : e[u]) {
        dfs_sz(it);
        sz[u] += sz[it];
    }
    sz[u]++;
}

void dfs_1(int u) {
    low[u] = sz[u] - 1;
    for (auto v : e[u]) {
        dfs_1(v);
        low[u] += low[v];
    }
}

void dfs_2(int u) {
    for (auto v : e[u]) {
        dp[v] = dp[u] + n - 2 * sz[v];
        dfs_2(v);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        ee[u].push_back(v);
        ee[v].push_back(u);
    }
    int root = 1;
    build(root);
    dfs_sz(root);
    dfs_1(root);
    dp[root] = low[root];
    dfs_2(root);
    long long ans = -1, ans_id = -1;
    for (int i = 1; i <= n; i++) {
        if (ans < dp[i]) {
            ans = dp[i];
            ans_id = i;
        }
    }
    cout << ans_id;
    return 0;
}

cpp

树形背包#

题目：P2014 选课

在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习．现在有 $N$ 门功课，每门课有若干学分，分别记作 $s_1,s_2,\cdots,s_N$ ，每门课有一门或没有直接先修课（若课程 $a$ 是课程 $b$ 的先修课即只有学完了课程 $a$ ，才能学习课程 $b$ ）．一个学生要从这些课程里选择 $M$ 门课程学习，问他能获得的最大学分是多少？

题目保证课程安排无冲突．（即不会有 $a$ 是 $b$ 的先修课， $b$ 也是 $a$ 的先修课这类情况存在．）

对于 $100\%$ 数据，保证 $1 \leq N \leq 300$ , $1 \leq M \leq 300$ , $1 \leq {s_i} \leq 20$ ．

数据保证至少存在一个 $k_i=0$ ，即至少一门课无先修课．

和01 背包相类似，定义 dp[t][k] 表示在以 t 为根的子树中，选择 k 门进行学习，所能够获得的最大分数．

此时，初始状态为 $dp[t][1]=s[t],t\in \mathbb{Z},1\leq t\leq n$ ，最终状态为 dp[root][m]，root 是根节点．

但状态转移方程是什么呢？

我们要将 k 门学习学科的配额进行有效分配．对于每一门学科，又可以分配 $[0,n]$ 个可学习配额，因此，有：

dp[u][k] = max(\sum_{u\rightarrow v} dp[v][a_i]) + s[u],0\leq a_i\leq k,\sum_{u\rightarrow v}a_i=k-1

，即：

对于每一种分配方案，为每一个子节点分配一定的可学习科目额度 $a_i$ ，所有可学习科目额度之和恰好等于 $k-1$ （这是由于节点 $u$ 必修，如果不修节点 $u$ ，则无法学习其子节点）
对于所有分配方案，取其中收益最大的

那要通过超高的时间复杂度来枚举每一种情况并计算吗？

我们可以引入一个辅助数组 g[m][k]，表示已经考虑 m 个 u 的子节点节点，且使用了 k 个学习配额，所能够获得的最大收益．

则有初始状态 $g[1][H]=dp[v_1][H],0\leq H\leq k$ ，此处 $v_i$ 表示节点 $u$ 的第 $i$ 个子节点．

不难发现状态转移方程： $g[m][H] = g[m-1][A]+dp[v_m][H-A],0\leq A\leq H$ ，其实就是在增加一个子节点时，枚举这个子节点所得的配额，用一种类似打擂台的方法统计出结果．使用完 g 数组后一定要清空！！！

利用 g 数组来优化 dp 的状态转移方程：

dp[u][k] = g[v_{max}][k-1] + s[i] $$，$v_{max}$ 为节点 $u$ 的子节点数量．必须选取节点 $u$，因为如果不选取节点 $u$，节点 $u$ 中的所有子节点都无法被选取． 标程：