树形dp学习笔记

Mr_Avalan · 2023-01-29 16:24:40 · 个人记录

树形dp学习笔记

注意，因为讲课人的水平实在太菜，这次的题目平均难度只有CF2000分。

树是一种十分甚至九分优美的结构，其本身子结构的性质让dp变得很可行。

从根节点出发，向儿子做深度优先搜索，用子节点的答案来合并更新父节点的答案，从而得到全局的答案。

也可以再从根到叶子节点更新以获取答案，这样的话前面的操作就可以认为是预处理。实际上感觉大多数树形dp都需要两次dfs

一般的树形dp可以把子树内的点和子树外的点分开考虑计算结果。

树形dp的状态多且杂。

一、普通树上dp

练习：

1. 洛谷p1352没有下司的舞会

经典的树形dp了。不会的建议删号重练。

code

2. 洛谷P8867建造军营

然后是大家非常熟悉和喜爱的 \text{NOIP2022 T3}，这道题需要先对图做边双，把它变成一棵树，再进行dp。
设 f[i] 表示 i 的子树里至少选了一个点，且所选的点到 i 的边都被选了的方案数。设 a[i] 表示子树里的桥边数量， b[i] 表示有多少点被缩到 i 里。
那么对于 f[u] 存在：

• 然后减去不选点构成的 $2^{a[u]}$ 种情况就可以了。 #### 问题是怎么统计答案。 我们对于每一个方案，只要在其点集的lca处统计答案即可。 换句话讲，对于节点 $u$ ，我们要计算点集的lca在 $u$ 的方案数。 再换句话讲，就是计算出在 $f[u]$ 中，$u$ 没被选而且只有一个子树中选了点的方案数，最后再用 $f[u]$ 减去它，乘上 $2^{m-a[u]}$ 的系数。 我们枚举 $u$ 的子节点 $v$ ， $v$ 的子树里有 $f[v]$ 种方案， $(u,v)$ 必选，其他边随意，有 $f[v]*2^{a[u]-a[v]-1}$ 种方案。 所以 $u$ 对最后结果的贡献就是 $(f[u]-\sum\limits_{v\in child(u)}f[v]*2^{a[u]-a[v]-1})*2^{m-a[u]}$ 。 最后对于连接边双内部的边显然是随便选，设有 $M$ 条桥边，就给最后的答案乘上 $2^{m-M}$ 即可。

code

二、树上背包

树上背包和普通背包不同点在于物品之间有相互的依赖关系。选取一个物品的必要条件是选取了所有他的所有祖先,因此只需要考虑选取当前物品对后续的影响即可。

练习：

1. 洛谷P2014 [CTSC1997] 选课

01背包的模板，设 dp[i][j] 为第 i 号节点的子树中有 j 个连续的节点被选了，而对于每一个内部有点被选的子树，其根节点都是必选的，所以可以把 dp[i][1] 设为该节点的权值，然后做背包就可以了。
注意，单次背包合并的复杂度是 O(n^2) ，需要合并 n 次，所以总复杂度为 O(n^3) 。其实不优化也能通过这道题。 但是我们可以舍弃一些无用的状态来优化dp。

这样就控制了 j 和 k 的上下界：

2. 所以 $dp[x][i+j][0][1]=\sum(dp[x][i][0][1]*(dp[v][j][0][1]+dp[v][j][1][1])+dp[x][i][0][0]*dp[v][j][1][1])$ 。 - 如果 $x$ 被监听了，放了装置，同样分情况
4. 所以 $dp[x][i+j][1][1]=\sum(dp[x][i][1][0]*(dp[v][j][1][0]+dp[v][j][1][1])+dp[x][i][1][1]*(dp[v][j][0][0]+dp[v][j][0][1]+dp[v][j][1][0]+dp[v][j][1][1]))$ 。 然后就可以做dp了。

code

三、换根dp

树形dp中的换根dp问题又被称为二次扫描，通常不会指定根结点，并且根结点的变化会对一些值，例如子结点深度和、点权和等产生影响。

一般来讲，换根dp需要先做一次dfs预处理，再更新答案，且用父节点更新子节点或用子节点更新父节点都是 O(1) 完成。

练习：

1. P3478 [POI2008] STA-Station

给出一个n个节点的树，找出一个节点为根，使得树上所有节点的深度之和最大。
我们先假设1号节点就是根节点，这时候，我们对树做一次dfs就可以求出每个点的子树的大小，并且同时也可以求出所有节点的深度之和。
这时候，如果我们把根节点转移到1号节点的一个儿子x上，那么x节点对应的所有以1为根节点的子树中的节点的深度都要减去1，而除了x以外的其他儿子节点和1节点的深度都要增加1，所以对应总的深度和就可以计算出来，也就是说通过父节点信息我们可以推算出子节点的信息，这样我们就可以在树上进行动态规划了。

code

2. P6419 [COCI2014-2015#1] Kamp

如果我们能算出对于一个点 u ，从它出发送完所有人再回到 u 的最短距离，再减去到这个点的最长链的长度，就是答案。

• 第一次dfs
  设 g[u] 表示以 u 为根的子树里从 u 开始把所有家在这个子树里的人送回家并回到 u 的最短路程。
  再设 siz[u] 表示家在以 u 为根的子树中的人数。
  所以 g[u]=\sum\limits_{v\in child(u)}g[v]+2*val[u][v] 。
  同时可以求得子树中的最长链和次长链，这对我们后续求全局的最长链是有用的。
• 第二次dfs
  设 f[u] 表示从 u 开始把所有人送回家并回到 u 的最短路程。 1、当没有人的家在 u 的子树里时， f[v]=f[u]+2*val[u][v] 。
  2、当所有人的家都在 u 的子树里时， f[v]=g[v] ，因为相当于所有的步数都变成下一步。
  3、其他情况，因为反正都要走两遍 val[u][v] ，所以 f[v]=f[u] 。
  接下来就可以考虑最长链和次长链了。
  设 len[u] 表示以 u 结束的最长链， slen[u] 表示以 u 结束的次长链， id[u] 表示以 u 结束的最长链的第一个节点。
  情况同上。
  1、 len[v]=len[u]+2*val[u][v] 。
  2、可以发现这种情况根本不需要更新。
  3、这种情况最为麻烦。
  1）当 len[u]+val[u][v]\ge len[v] 且 id[u]\ne v 时，更新。
  2）当 slen[u]+val[u][v]\ge len[v] ，更新。
  3）当 len[u]+val[u][v]\ge slen[v] 且 id[u]\ne v 时，更新。
  4）当 slen[u]+val[u][v]\ge slen[v] 时，更新。
  这样第二次dfs就做完了。

code

四、虚树

有时我们会遇到一些多次询问的树形dp，当每一次询问只涉及树上少量节点时，我们并不需要对整棵树进行dp。我们可以建立一棵仅包含少数关键点的虚树，将非关键点收缩成边或者直接删去，这样可以减少时间上的消耗。

如何建立虚树

最右链是虚树构建的一条分界线，意为在最右链左侧的点都已经建好虚树。我们可以用一个栈 sta 来维护最右链， top 为栈顶。

注意，最右链上的边并没有被加入虚树，因为随时都可能有点被弹出。

假设现在已经考虑到了 now 号节点， now 和 sta[top] 的lca是 lc 。
由于 lc 是 sta[top] 的祖先，所以它一定在我们维护的最右链上。
分情况讨论：

1.  此时直接把 $now$ 加在 $sta$ 的末尾即可。
2.  此时 $sta[top]$ 已经不在最右链里了，所以把边 $lc-sta[top]$ 加入虚树，然后把 $sta[top]$ 出栈，把 $lc$ 、 $now$ 加入最右链。
3.  跟上一种其实是一样的，但是 $lc$ 不用再加入最右链了。
4.  此时我们需要把 $lc-sta[top]$ 之间的所有边都加入虚树，再全部出栈，最后加入 $lc$ 和 $now$ 。

对于每一个询问，我们需要的虚树也不同，但是不能直接对虚树进行清空，这样的复杂度会退化到 O(n) ，只要在dfs时一边访问一边清空就好了。

练习：

1. P2495 [SDOI2011] 消耗战

我们可以对每个点预处理出 mn[u] 表示 u 到 1 的路径上最小的边权。
对每次询问建立虚树，如果 u 是询问的点，那么切断 u 与其子树上的询问点的最小花费 dp[u]=mn[v] ,否则 dp[u]=min(mn[u],\sum\limits_{v\in child(u)}dp[v]) 。

code

一些题目

P8916 [DMOI-R2] 暗号

题目大意：有一棵树，给一棵 n 个节点的树，每个节点有一个权值。要求给这 n 个节点黑白染色。两个拥有相同颜色的节点中，深度较小的结点的权值加上子树中颜色与它相等的节点初始值,求权值和的最大值。
长沙王讲过就不讲了。
设 dp[u][j][k][0/1] 表示 u 到根的路径上 j 个连续的黑色， k 个连续的白色， u 节点染成黑或白。
那么

P4099 [HEOI2013]SAO

题目大意：有一个 n 个节点的树形图，求它有多少中拓扑序。
想容斥的同学自己切掉就好了，不要声张。
设 dp[u][i] 表示在 u 的子树里 u 的排名为 i 的方案数。
我们让 u 和他儿子 v 合并，也就是用 dp[v][j] 来更新 dp[u][i]。
有两种情况：

1. 枚举 $k$ 表示 $v$ 的子树里有 $k$ 个在 $u$ 前面，所以： $$dp[u][i+j]+=dp[u][i]*dp[v][k]*C_{i+j-1}^{i-1}*C_{siz[u]+siz[v]-i-j}^{siz[u]-i}$$ 用个前缀和就可以把 $k$ 这一维删掉。
2. 和1差不多，不想讲了。
   同样用后缀和可以删掉一维。

CF337D Book of Evil

题目大意：一棵 n 个节点的树，有一些点被标记，问有多少点离所有被标记的点的距离都小于 d 。
设 dp[u][0] 表示从 u 到其子树里最远的被标记的点的距离， dp[u][1] 表示从 u 到其另一个儿子的子树里最远的被标记的点的距离。
设 dis[u] 表示从 u 到其子树以外的被标记的点的最远距离。