树形DP

  |  

摘要: 树形DP的思想与经典问题

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


树形DP思想

在树形结构上求解问题,在某棵以 u 为根的树上的答案为 dp[u],其重复子问题是子树上的问题,对应的答案为 dp[v]。状态转移方向就是从子节点到父节点,当前以 u 为根的树拿到各个以 v 为根的子树的答案后进行整合,形成当前树的答案,然后继续向上传。状态转移方程大致是下面这样的形式:

1
2
3
4
dp[u][s] = 常数                    u为叶子节点
= f(dp[v1], dp[v2], ...) v1,v2,...为u的子节点
s 为与 u 相关的状态
答案 g(dp[root])

以求树高为例,转移方程如下:

1
2
3
4
5
6
7
8
9
10
11
状态定义:
dp[u] := 子树 u 的高度

答案:
dp[root]

初始化:
dp[u] = 1; u 为叶节点

状态转移:
dp[u] = max(dp[v] + 1); v 为 u 的子节点。

有时候子树的答案交给当前根之后就不会再用到了,这种情况有点像后序遍历处理的问题,此时一般就用后序遍历而不提树形DP的事,例如 树的高度 以及 树的DFS遍历 中后序遍历部分的问题。

阶段和附加状态

从阶段和附加状态的角度看,树形 DP 的阶段是树的深度,节点的具体位置是附加状态。对应到 dp[u] 中,u 相当于附加状态,但其中隐含了阶段。

状态计算顺序

  • 自顶向下:记忆化搜索
  • 自底向上:拓扑序

dpupdpdown

在有的问题中,树形 DP 状态设计要分为 dpupdpdown 并且转移的时候分成两步 dfs 来做(有时通过一些推导也可以变成一趟dfs),称为二次扫描与换根法。参考文章 二次扫描与换根DP


树形DP解决的经典问题

1. 树的高度

本题直接后序遍历即可。

2. 树的最长链

本题相关的内容参考文章 【树形DP】树的直径

3. 某点到所有点的最大距离最小

本题相关的内容参考文章 二次扫描与换根DP

4. 同色最长链

与普通最长链的区别是取 $v \in son[u]$ 时,取同色的 $v$。

5. 树的重心

树的重心定义:最大子树最小。算法如下:

1
2
3
4
5
状态定义:
dp[u] = 以 u 为根的子树的最小

状态转移:
dp[u] = (max(dp[v]), n - dp[u]); v 为 u 的子节点

6. 最大点独立集

最大点独立集定义:两两无边相邻。

此问题在一般图上很难做,在树上和二分图上可做,最简明的是在树上做。

不能简单地将树分层。算法如下:

1
2
3
4
5
6
7
8
9
10
11
12
状态定义:
dp[u][0] := u 不选的最大点独立集
dp[u][1] := u 选的最大点独立集

状态转移:
dp[u][0] = 0 u 为叶子节点
= sum(max(dp[v][0], dp[v][1])) v 为 u 的子节点

dp[u][1] = 1 u 为叶子节点
= sum(dp[v][0]) + 1 v 为 u 的子节点

答案:max(dp[root][0], dp[root][1])

7. 最小点覆盖集

最小点覆盖集定义:点集覆盖了所有的边,即对于 $G = (V, E)$ 中任意 $e=uv \in E$,$uv$ 中至少有一个在点集中。

算法如下:

1
2
3
4
5
6
7
8
9
10
11
状态定义:
dp[u][0] := u 不选的最小点覆盖集
dp[u][1] := u 选的最小点覆盖集

状态转移:
dp[u][0] = 0 u 为叶子
= sum(dp[v][1]) v 为 u 的子节点
dp[u][1] = 1 u 为叶子
= sum(min(dp[v][0], dp[v][1])) + 1

答案:min(dp[root][0], dp[root][1])

8. 最小点支配集

最小点支配集定义:所有的点,要么属于支配集,要么与支配集中的点相连。

比较复杂的地方:对于 u,有可能不属于支配集合,并且子节点也不属于支配集合,但是父节点属于支配集合。这种情况在转移的时候必须注意,dp状态,需要增加一维表示 u 的子节点是否属于支配集(u 是否被支配)。

算法如下:

1
2
3
4
5
6
7
8
9
10
11
状态定义:
dp[u][0] := u 选了
dp[u][1] := u 未选,但是 u 被支配了(u 的子节点中有属于支配集的)
dp[u][2] := u 未选,且 u 未被支配

状态转移:
dp[u][0] = sum(min(dp[v][0], dp[v][1], dp[v][2])) + 1
dp[u][2] = sum(dp[v][1])
dp[u][1] := 至少有一个 son(u) 中的 v 被选了

答案: min(dp[root][0], dp[root][1])

dfs 在枚举 $v \in son(u)$ 过程中维护 tmp = sum(min(dp[v][0], dp[v][1])),记一个 flag 表示是否有某个 v,$dp[v][0] \leq dp[v][1]$。

若 flag 被触发,则 dp[u][1] = tmp 即可,因为 tmp 记录的情况已经有 v 被选了。

若 flag 未触发,则对所有 v,均有 $dp[v][0] > dp[v][1]$,但是必须要选一个,就看哪个 v 的 $dp[v][0] - dp[v][1]$ 更小。

因此状态转移中 dp[u][1] 的转移方程如下:

1
2
dp[u][1] = tmp     f被触发
= min(tmp - dp[v][1] + dp[v][0]) f未被触发

u 为叶子的边界条件:

1
2
3
dp[u][0] = 1
dp[u][1] = +INF
dp[u][2] = 0

力扣 968. 监控二叉树 是相关的一道题,题解参考文章 【树形DP】力扣968-监控二叉树

9. 有依赖的背包

树形背包问题相关的内容参考文章 树形背包


题目

本题相关的内容参考文章 二次扫描与换根DP

本题相关的内容参考文章 拓扑排序的方案数

本题相关的内容参考文章 力扣1617-计子树中城市之间最大距离


Share