什么是树形 DP？

树形 DP（Dynamic Programming on Trees）是一种在 树结构 上使用 动态规划 解决问题的方法。它的核心思想是 自底向上 递归计算，每个节点的状态依赖于它的子节点的计算结果。

如果你熟悉普通的 动态规划（DP），你可以把树形 DP 理解为：

• 普通 DP 在一维或二维数组上进行（如最长子序列、背包问题）。
• 树形 DP 在树的节点之间进行（如子树计算、路径问题）。

树形 DP 的应用场景

树形 DP 主要用于 涉及树结构的最优决策问题，常见的题目类型包括：

1. 树的最小覆盖问题

题目： 选最少的节点，使得树中的所有边至少有一个端点被选。 解法： 定义 dp[u][0] 表示 u 不选，dp[u][1] 表示 u 选，递归计算。

2. 树的最大权路径和

题目： 给定一棵树，每条边上有权重，求从某个节点出发的最长路径。 解法： dp[u] 代表以 u 为根的子树的最长路径，递归求解。

3. 树的直径（最长路径）

题目： 求一棵树中两点之间的最长路径。 解法： 两次 DFS 或树形 DP 计算最长路径。

4. 树的最小删除代价

题目： 删除最少的节点，使得树变成某种结构（如二叉树）。 解法： dp[u] 表示删掉 u 的最小代价。

5. 祖先/子孙信息计算

题目： 计算树上每个节点的子孙数量、深度等信息。 解法： dp[u] 递归计算 u 的子树大小。

树形 DP 的基本步骤

1. 建树（用邻接表存储）。
2. 定义 DP 状态（每个节点可能有多种状态，如放置与不放置士兵）。
3. 递归计算 DP（从叶子节点开始往上计算）。
4. 返回根节点的最优解（一般是 min(dp[root][0], dp[root][1])）。

总结

树形 DP 是在树上进行的动态规划，通常用于计算子树信息、自底向上的最优决策，在树的路径问题、覆盖问题、删除问题、优化问题等场景中非常常见。它的核心是 递归计算每个节点的状态，并将结果传递给父节点。

安装

使用 go install （推荐）

使用 go 1.23 或更高版本:

go install github.com/air-verse/air@latest

使用方法

只需执行 air 命令

air

文档

GitHub URL: https://github.com/air-verse/air
README: https://github.com/air-verse/air/blob/master/README-zh_cn.md

url: https://www.luogu.com.cn/problem/P1074

tag:
NOIP2009 提高组，搜索，剪枝，位运算，NOIP提高组，2009

思路：

1. 核心变量解析

• a[10][10]：存储数独棋盘，ai表示第i行第j格的数字（0表示空格）
• r[10]：行约束，r[i]的二进制第k位表示第i行能否填数字k+1（1表示可用）
• c[10]：列约束，c[j]的二进制第k位表示第j列能否填数字k+1
• e[5][5]：九宫格约束，ex的二进制第k位表示第x行第y列九宫格能否填k+1
• p[1<<11]：位掩码到数字的映射，p[1<<k]=k+1（快速获取候选数字）
• o[1<<10]：预计算二进制中1的个数，o[mask]表示mask的候选数字个数
• ans：存储最终的最大得分

2. 关键函数解析

• gs()：根据位置计算得分，边缘得分低，中心得分高（计算公式：值*(6+距边缘距离)）
• init()：初始化约束为全可用状态，预处理o[]和p[]的映射关系
• dfs()：采用最小候选数优先的回溯算法，通过位运算快速枚举候选值

3. 算法流程

• 预处理所有约束条件
• 优先选择候选数最少的格子进行填充（剪枝优化）
• 用位运算快速遍历所有候选数字
• 递归搜索时动态更新约束条件
• 达到填满状态时更新最大得分

4. 位运算优化点

• 用异或操作快速增删约束条件（r[i]^=mask）
• 用lowbit技巧遍历候选数字（t&-t获取最低位的1）
• 预计算o[]避免重复计算候选数个数

参考： https://www.luogu.com.cn/article/gerq24ll
ps: 好强大的位运算思路，爱了爱了。

代码：

#include <iostream>
using namespace std;
int a[10][10], r[10], c[10], e[5][5], p[1 << 11], ans = -1;
int o[1 << 10];
int gs(int i, int j)
{
    return a[i][j] * (6 + min(min(i, 8 - i), min(j, 8 - j)));
}
void init()
{
    for (int i = 0; i < 9; i ++) r[i] = c[i] = e[i / 3][i % 3] = (1 << 9) - 1;
    for (int i = 0; i < (1 << 9); i ++)
    {
        int t = i;
        while (t)
        {
            t &= t -1;
            o[i] ++;
        }
    }
    for (int i = 0; i < 9; i ++) p[1 << i] = i + 1;
}
void dfs(int cnt, int sum)
{
    if (cnt == 0)
    {
        ans = max(ans, sum);
    }
    int mi = 10, x, y;
    for (int i = 0;  i< 9; i++)
        for (int j = 0; j < 9; j ++)
        {
            if (!a[i][j])
            {
                int t = r[i] & c[j] & e[i / 3][j / 3];
                if (o[t] < mi)
                {
                    mi = o[t], x = i, y = j;
                }
            }
        }
    int t = r[x] & c[y] & e[x / 3][y / 3];
    while (t)
    {
        int l = (t & -t);
        t -= l;
        a[x][y] = p[l];
        r[x] -= l, c[y] -= l, e[x / 3][y / 3] -= l;
        dfs(cnt -1, sum + gs(x, y));
        a[x][y] = 0;
        r[x] += l, c[y] += l, e[x / 3][y / 3] += l;
    }
}
int main()
{
    init();
    int cnt = 0, sum = 0;
    for (int i = 0; i < 9;  i++)
        for (int j = 0; j < 9; j ++)
        {
            cin >> a[i][j];
            if (a[i][j])
            {
                r[i] -= 1 << a[i][j] - 1;
                c[j] -= 1 << a[i][j] - 1;
                e[i / 3][j / 3] -= 1 << a[i][j] -1;
                sum += gs(i, j);
            }else cnt ++;
        }
    dfs(cnt, sum);
    cout << ans << endl;
    return 0;
}

url: https://www.luogu.com.cn/problem/P2476

tag:
SCOI2008，动态规划，搜索，记忆化搜索

思路：
开一个6维的数组来表示状态（因为每种情况有多种，所以不能用压位bit），分别表示足够涂1， 2， 3， 4， 5块木头的颜色有几种，最后一维表示上一种颜色的种类。然后用记忆化搜索来做。参考： https://www.luogu.com.cn/article/fhusu9wq

代码：

#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
ll MOD = 1e9 + 7;
int n, t[6];
ll dp[16][16][16][16][16][6];
ll dfs(int a, int b, int c, int d, int e, int last)
{
    if (dp[a][b][c][d][e][last] != -1) return dp[a][b][c][d][e][last];
    if (a + b + c + d + e == 0) return 1;
    ll res = 0;
    if (a) res += (a - (last == 2)) * dfs(a - 1, b, c, d, e, 1);
    if (b) res += (b - (last == 3)) * dfs(a + 1, b - 1, c, d, e, 2);
    if (c) res += (c - (last == 4)) * dfs(a, b + 1, c - 1, d, e, 3);
    if (d) res += (d - (last == 5)) * dfs(a, b, c + 1, d - 1, e, 4);
    if (e) res += e * dfs(a, b, c, d + 1, e - 1, 5);
    dp[a][b][c][d][e][last] = res % MOD;
    return dp[a][b][c][d][e][last];
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++)
    {
        int a;
        cin >> a;
        t[a] ++;
    }
    memset(dp, -1, sizeof dp);
    ll ans = dfs(t[1], t[2], t[3], t[4], t[5], 0);
    cout << ans << endl;
    return 0;
}

url: https://www.luogu.com.cn/problem/P1278

tag:
记忆化搜索，状压DP

思路：
记忆化搜索，dfs两个参数一个是当前的字母，另外一个是当前的状态。f[x, y] 表示当以字符串x开头是状态为y时最大的字符串长度。

代码：

#include <iostream>
#include <vector>
using namespace std;
string st[18];
vector<int> v[210];
int f[17][1 << 17];
int n, ans;
int dfs(int x, int y)
{
    if (f[x][y]) return f[x][y];
    int res = 0;
    for (auto i : v[st[x][st[x].size() - 1]])
        if (!((y>>(i - 1) & 1))) res = max(res, dfs(i, y | 1 << (i - 1)));
    return f[x][y] = res + st[x].size();
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> st[i], v[st[i][0]].push_back(i);
    for (int i = 1; i <= n; i ++) ans = max(ans, dfs(i, (1 << (i - 1))));
    cout << ans << endl;
    return 0;
}