树形DP 换根DP 树形背包

_Cheems · 2023-08-04 22:05:43 · 个人记录

前言

夏令营某天，zsq：大家今晚复习树形 dp，明早测试。

我：啊？什么东西（马上搜索树形 dp）

部分内容借鉴了网络资源，以及曹文、李建等人所著的《信息学奥赛一本通提高篇》。

介绍

概念

顾名思义，就是在树上做 \operatorname{dp}。

显然，树中的父、子节点关系满足子问题关系。与线性 \operatorname{dp} 的顺推逆推类似，树形 \operatorname{dp} 也有两种转移方向。
1. 子节点转移至父节点：将子节点的信息转移至父节点，如树形背包问题。
  
  在遍历子节点后，整理信息至父节点。
2. 父节点转移至子节点：将父节点转移至子节点，应用于换根 \operatorname{dp} 中。
  
  先得出父节点的信息，再转移至子节点，往往需要考虑信息重复的问题。
时空复杂度

一定有第一维 [u] 代表树上每个节点。

第二维 [k] 视情况而定，通常表示容积、最长链点数等，变化多端。

除此之外，对于一些复杂问题往往会有多组 \operatorname{dp} 数组，以及树上常用数据（深度、子树大小等）。

由于每个点只会被父节点访问一次、作为其它点的父节点一次，因此时间复杂度是 O(n) 的。如有第二维，则时间复杂度为 O(nk)。

例题分析

在此之前，定义：v∈u，当且仅当 v 为 u 子节点。

朴素树形 \operatorname{dp}

最常见的树形 \operatorname{dp} ，即由子节点传至父节点。
例题 P2016 战略游戏

大意：给出一棵树，选择一些特殊点，每个特殊点可以覆盖相连之边。求覆盖所有边的最小特殊点数？

思路：需要在树型结构上求最值，而且与每个点的取舍有关，考虑树形 \operatorname{dp}。

定义 dp[u][0/1] 代表：以 u 为根的子树中，u 是否为特殊点时（ 0 不放，1 放），覆盖子树所有边的最小花费。

然后分类讨论：
整理得：
dp[u][0]=\sum\limits_{v_i∈u}dp[v_i][1] dp[u][1]=\sum\limits_{v_i∈u}min(dp[v_i][0],dp[v_i][1])
主要代码如下：
```
void dfs(int u,int fa){
  dp[u][1]=1; //初始值一定要注意
  for(int i=head[u]; i;i=e[i].nxt){
      int v=e[i].v;
      if(v^fa){
          dfs(v,u);
      }
  }
  for(int i=head[u]; i;i=e[i].nxt){
      int v=e[i].v;
      if(v^fa){
          dp[u][1]+=min(dp[v][0],dp[v][1]);
          dp[u][0]+=dp[v][1];
      }
  }
}
```
树形背包

树形 \operatorname{dp} 与背包问题的结合，即每次转移均做一次背包。

也可视为依次合并子树，并更新合并后的值，也就是说 siz[u] 的值是动态变化的。

仿照 \operatorname{01} 背包倒序枚举的写法，可忽略掉 \operatorname{dp} 数组关于时间轴的一维。

转移方程如下：

这样写要用滚动数组 a：
dp_{u,i+j}=\max\limits_{v∈u,i≤min(k,siz[u]),j≤min(k,siz[v]),i+j\le k}a_{u,i}+dp_{v,j}
这样写要倒序枚举，时间有时会挂：
dp_{u,i}=\max\limits_{v∈u,i≤min(k,siz[u]),j≤min(i,siz[v])}dp_{u,i-j}+dp_{v,j}
没啦~

时间复杂度的分析：

看似是 O(n^3) 的复杂度，但真是如此吗？

首先，任意两点只会在其 \operatorname{LCA} 处合并，合并后信息传递至 \operatorname{LCA}，故不再被合并，因此所有点合并次数为 n。

所以时间复杂度是 O(nk^2)？事实上是 O(nk)。

对每次合并进行讨论，不妨设两棵子树的大小分别为 x 与 y，显然合并两背包的时间复杂度为 O(xy)。

然后对 x、y、k 的大小关系分类讨论。
所以想写对时间的话，一定要卡好每次循环的上下界。
例题 P4516 潜入行动

普通树形背包题。

定义 f_{u,i,0/1,0/1} 表示以 u 为根的子树中，安装了 i 个装置，点 u 是否安装装置、是否被覆盖，且除根外的节点均被覆盖时的方案数。

状态转移时需注意如下要点，别写着写着就搞错了：
- 对于子节点而言：子节点状态已经确定，也就是根节点的状态不能与其产生矛盾（例如：根节点安装装置的状态，不能由子节点不被覆盖的状态转移而来）。
- 对于根节点而言：“是否安装装置”这一状态已经固定，但“是否被覆盖”这一状态是可以变的（例如：现在根节点被覆盖的方案数，可由原先根节点未被覆盖的方案数 × 子节点安装装置的方案数得来）。
还有，这道题要用滚动数组进行正向枚举，常规的逆向枚举会 \rm {TLE}。这让我们了解到正逆两种枚举方式的不同（逆向枚举可能会枚举到一些无效状态，避免这一点也是可以过的）。

要注意的就这几点，可自行推导后翻阅题解比对。
换根 \operatorname{dp}

在该题型中，需求出以不同节点为根时所要求的值。

解决此类题型的套路是：先由叶到根求出以 u 为根的子树的某种值 g_u，再由根到叶求出 u 作为整棵树的某种值 f_u，一般通过容斥原理求 f_u（其实就是去掉重复值）。

预处理后再做一次 \operatorname{dp}，此时处理的是父节点转移至子节点。

换根 \operatorname{dp} 思维量较大，掌握根之间的转换是解题的重要步骤。
例题 P9437 一棵树

大意：看题目，很清晰。

思路：考虑换根 dp。

以下所提的 a[i] 为原题的定义。

值得一提的是 e(u,u) 也算合法路径。

定义以下数组：
到达 u 的路径值 P，可理解为一个以 u 结尾的数（题意）。

之所以这样定义，是为了简化转移操作。如果存在 e(u,v)，则路径值 P2=d[v]*P+a[v] 。

转移方程的推导：

建议画图推导。
- $g[u]=\sum\limits_{v_i∈u}g[v_i]*d[u]+siz[v_i]*a[u]
- 令 $fa$ 为 $u$ 的父节点，遍历 $u$ 时已经得到 $f[fa]$。为了方便处理，我们先得出除 $u$ 子树外的所有点到 $fa$ 的路径值之和 $S$，再由 $S$ 得到 $f[u]$。如图所示，$S$ 又可分为 $A$（蓝）、$B$（红）两部分，主意 $fa$ 同时处于 $A$、$B$ 中： ![](https://cdn.luogu.com.cn/upload/image_hosting/nurn6h62.png?x-oss-process=image/resize,m_lfit,h_170,w_225) 显然，$A=f[fa]$。而 $B$ 的含义是：$fa$ 子树中，除 $u$ 子树外的所有点至 $fa$ 的路径值之和，考虑大减小： * 红色部分：$g[fa]
  - 黄色部分：g[u]*d[fa]+siz[u]*a[fa]，此处不是指黄点至 u 的路径和，而是指黄点至 fa 的路径和，因此要多算上 a[fa]。
  于是：
  B=g[fa]-(g[u]*d[fa]+siz[u]*a[fa]) S=A-B==f[fa]-(g[fa]-(g[u]*d[fa]+siz[u]*a[fa]))
  注意 e(fa,u) 会被经过 n-siz[u] 次，即树上除 u 子树外的所有点。
  
  所以：
  f[u]=d[u]*S+(n-siz[u])*a[u]
  大功告成！
代码的所有重要部分已被推导出。至于具体实现，太过复杂故不展示。

树形DP 换根DP 树形背包

前言

介绍

概念

时空复杂度

例题分析

朴素树形 \operatorname{dp}

树形背包

换根 \operatorname{dp}