换根 DP：进阶练习笔记

· · 算法·理论

前言

观前提醒：本文非新手向文章，不建议作为换根 DP 入门使用。

本文在洛谷专栏、博客园、CSDN同步发送。

换根 DP 是树状 DP 的一种，思维难度较高，但是学会以后很套路也很轻松。

例题

P3047 [USACO12FEB] Nearby Cows G

对于每个节点求出距离它不超过 k 的所有节点权值和 m_i。

> 数据范围：$n \le 10^5, k \le 20$。 $\longrightarrow$ 算法时空复杂度很可能是 $O(nk)$。 对以 $1$ 为根的答案设计状态：由上文，首先考虑设计一个 $n \times k$ 的状态，根据套路设计 $f(x,d)$ 表示与 $x$ 距离不超过 $d$ 的节点权值和。 第一次 DFS 的转移方程：$f(x,d)=\sum_{x \rightarrow y} f(y,d-1)$。 然后 $ans(1,i)=f(1,i)$。 考虑第二次 DFS，**利用“父子贡献传递”的思想，考虑父节点 $x$ 变成子节点 $y$ 的子节点时会发生什么**。 首先 $f(y,k)$ 表示 $y$ 的子树的答案，但实际上应该加上把 $x$ 也看成子树的贡献。 而把 $x$ 看成 $y$ 子树的贡献相当于 $x$ 的原树 $ans(x,k-1)$ 失去了以 $y$ 为根的子树 $f(y,k-2) $后的 $f'(x,k-1)$。 此时这个 $f'(x,k-1)=ans(x,k-1)-f(y,k-2)$，所以 $ans(y,i)=f(y,i)+ans(x,i-1)-f(y,i-2)$。 答案即为 $ans(i,k)$。 > 问：能否只用一个数组 $f$，而不用开 $ans$？ > > 答：可以。 在这样的换根 DP 中，**以一个节点为根的答案在进入到这个节点之前就已经确定**，是不会变的。**所考虑的只有 $f(y,i)$ 在转移时的新旧互相影响过程**； 在上面的方程中，$ans(y,i)=f(y,i)+ans(x,i-1)-f(y,i-2)$ 可以看到，新值=原来值+无所谓反正不变的值-旧值。**每次用更新新值的必须是未被更新过的旧值**，模仿 $01$ 背包压维的过程，**倒序遍历**更新即可完美解决这个问题。 原代码第二次转移： ```cpp ans[y][0]=c[y],ans[y][1]=f[y][1]+c[x]; for(int j=2;j<=k;j++) ans[y][j]=f[y][j]+ans[x][j-1]-f[y][j-2]; ``` 新代码第二次转移： ```cpp for(int j=k;j>=2;j--) f[y][j]+=f[x][j-1]-f[y][j-2]; f[y][0]=c[y],f[y][1]+=c[x]; ``` ### [AT_dp_v Subtree](https://www.luogu.com.cn/problem/AT_dp_v) 若只题目，逆元不模质数。 “**对于每一个节点**” $\longrightarrow$ 尝试换根 DP。 数据范围：$n \le 10^5$ $\longrightarrow$ 时空复杂度 $O(n)$（因为换根 DP 一般都是 $O(n)$）。 对第一次 DFS 设计状态：套路设计，$f_i$ 表示以 $i$ 为根的子树的答案（$i$ 强制染黑）。 转移方程：某个点 $x$ 染成黑色以后，子树要么不染（$1$ 中方案），要么染黑的时相连的（$f_y$ 种方案），所以 $f_x = \prod_{x \rightarrow y} (f_y+1)$。 第二次 DFS：**利用“父子贡献传递”的思想，考虑父节点 $x$ 变成子节点 $y$ 的子节点时会发生什么**。 $f_y$ 应该乘上 $f^*_x+1$，而 $f^*_x$ 表示 $x$ 没有以 $y$ 为根的子树时的答案，为 $\frac{f'_x}{f_y+1}$，即 $f'_y = f_y \times (\frac{f'_x}{f_y+1}+1)$。 但是，**这道题的模数 $m$ 不！是！质！数！**，所以没法逆元。 考虑 $f'_x$ 的来源：$f'_x=$ $x$ 原父节点的贡献 $\times$ $x$ 原子节点的贡献，所以 $f^*_x=$ $x$ 原父节点的贡献 $\times$ $x$ 除了 $y$ 的原子节点的贡献。 又因为 **$x$ 除了 $y$ 的原子节点的贡献 $=$ $x$ 在 $y$ 左侧子节点的贡献 $\times$ $x$ 在 $y$ 右侧子节点的贡献，所以可以分别记录 $x$ 子节点贡献的前后缀和 $fl$ 和 $fr$**，因为最后还要乘上 $x$ 原父节点的贡献，所以这也要单独记录为 $up_x$（此时可以发现 $up_y = f^*_x+1$）。 最后新的方程为 $up_y = fl_{pre(y)} \times fr_{next(y)} \times up_x +1$，$f'_y = f_y \times up_y$。 可以发现这道题中也是 **$y$ 的所有状态都在进入 $y$ 之前确定，且 $y$ 的新状态只与 $y$ 的原状态和 $x$ （不会变的）原状态有关**，所以 $f'$ 和 $f$ 可以压成一个数组表示。 ### [P6419 \[COCI 2014/2015 #1\] Kamp](https://www.luogu.com.cn/problem/P6419) 独立切的紫，爽！ 题目要求“对点 $i = 1 \sim n$” 均求出答案，所以考虑换根 DP。 #### I. 简化树 首先，要遍历树上一些点，**可以联想到一个结论：“遍历树上所有点（实际上是所有叶节点），最后回到原位所需的最小总路程为树边权和的两倍”**，但是这个结论中的情况仍和本题有所不同。 + 本题中**不需要遍历所有点，而只需要遍历有标记的点即可**。针对这个情况，需要找到那些不必遍历的点——这些点不在任何两个标记点的路径上。 + 本题中**不需要回到原位**，所以答案应为：两倍边权和减最后一个点的深度。 对于第一种情况，这类非必要点分布在两个位置：（1）没有标记点的子树中，这时可以直接砍断这个子树；（2）从根节点（含）到所有标记点的 LCA（不含）的所有点。 对于上述（2）情况，只要一开始把根设置成必要点上，那么（2）点就不存在，缩减了讨论范围。所以可以尝试从第一个标记点的位置开始遍历，以它为根。 这样我们就获得了一棵简化树，**遍历这棵树上的所有节点也就相当于是完成了题目中的任务**。 #### II. 必要点 因为答案为“两倍边权和减最后一个点的深度”，两倍边权和是定值，所以要使得最后一个点的深度最大，答案才能最小。 于是自然会选择**让最深的一个点作为最后一个点**（废话），考虑如何找到**以每个（必要）点为根时，简化树上最大深度点的深度**（问题转化）。 最初提到“尝试使用换根 DP”，于是用 $f_x$ 表示以 $x$ 为根的子树中最深节点的深度。那么有 $f_x = \max_{x \xrightarrow{z}{y}} f_y+z$。 第二次转移：对于每一条边 $x \xrightarrow z y$，$f'_y$ 来自两部分，（1）原本的子树 $f_y$，（2）把 $x$ 看作 $y$ 的子树后新的贡献 $f^*_x$——$x$ 除去 $y$ 后的后代最大深度。 核心是如何从 $f^*_x$ 中排除 $y$ 的影响，我先后使用了两种方法：（1）事先将 $x$ 的所有子树按照 $f$ 值从大到小**排序**，如果 $y$ 为第一个子节点则取第二个子节点（如果该节点存在）的 $f$ 值；（2）将 $f$ 改为**同时处理最大和次大值**，然后将 $f_y$ 与最大值判断以确定最大值是否由其转移而来，否则取最大值，是则取次大值。 然后我们就获得了所有必要点的 $f'$ 值，$(2\sum z) - f'_x$ 即为 $x$ 节点上的答案。 同上几题，$f$ 和 $f'$ 也都可以压成一个数组。 #### III. 非必要点 非必要点的策略很简单：一直走到必要点上，然后像正常点那样走，答案也就是这个必要点的答案加上额外走的距离。 一共需要四个 DFS，简化树一个，必要点换根 DP 两个，非必要点统计答案一个。不过前两个和最后两个 DFS 似乎可以分别压在一起。 本题总体思路：**联想到结论，简化树，尽量把所求值往结论上靠→成功转化题意，将所求答案分成两类，换根 DP 求出其中一类，另一类随便乱搞**。 ### [P3647 \[APIO2014\] 连珠线](https://www.luogu.com.cn/problem/P3647) 好题，当赏👍。 #### 状态表示 样例图示： ![](https://cdn.luogu.com.cn/upload/image_hosting/urv40lm2.png) 首先这个游戏构造出的一定是一个树。 因为游戏要求是“从**一个**珠子开始，每次会用如下方式添加**一个**新的珠子”，也就是说每次然后如果把第一个点作为树的根节点，那么 `Append` 操作只能给父节点添加子节点，`Insert` 操作只能在父子节点间进行。 最后同一次操作中构造出的蓝线一定是以连接“父—子—孙”的形式存在。 当在树上一条链上走的时候，这个东西有点像奇偶变换：父/孙→子→父/孙→子→……（孙子节点同时是下一段链的父节点）。所以初步估计要设计的状态有两层：$f_{x,0}$ 表示 $x$ 作为父/孙节点时的答案，$f_{x,1}$ 表示其作为子节点时的答案，两者互相转换。 > 后来我在题解区找到了一个意义相同但更加准确的表达：$f_{x,0}$ 表示 $x$ 作为端点时的最大的分，$f_{x,1}$ 表示 $x$ 作为中点时的最大得分。 #### 状态转移 当一个节点作为父/孙节点的时候，它可以作为任意多条蓝链的端点，所以 $f_{x,0}=\sum (f_{y,1}+z)$。 但是这个转移方程并不完善，因为有可能 $y$ 不能作为链中点（比如说 $y$ 没有子树的情况）。按照 DP 的惯例，$f_{y,1}$ 应该等于 $-\infin$，$f_{x,0}$ 也就变成 $-\infin$ 了；还有另外一种可能，那就是 $y$ 作为父/孙节点时赚的更多。 综上所述，**DP 的时候绝不能轻易省略转移来源**。设 $s(y)=\max\{f_{y,1}+z,f_{y,0}\}$，更完整的方程应该是 $f_{x,0} = \sum s(y)$。 然后来考虑当 $x$ 作为子节点时如何转移。$x$ 作为链中点的时候，后面必须要跟至少一个端点 $y_0$，那么方程如下： $$f_{x,1} = \max_{y_0}\left\{ f_{y_0,0} + \sum_{y \neq y_0} s(y) \right\}$$ 但是这个方程太恶臭了，观察发现后面的 $\sum_{y \neq y_0} \max\{ f_{y,1}+z,f_{y,0} \}$ 其实就是 $f_{x,0}-\max\{ f_{y_0,1}+z,f_{y_0,0} \}$，其中 $f_{x,0}$ 是定值，可以提到外面去，于是有： $$f_{x,1} = f_{x,0} + \max\left\{ f_{y_0,0}-s(y_0) \} \right\}$$ 这样就可以快速转移了。 #### 换根 DP 但是，上面的一切推论都是建立在第一个点（也就是树根）确定的基础上，然而本题中树根并不确定，所以可以尝试用换根 DP 统计出每一个点作为根的答案，再取最大值作为答案。 利用“父子交换贡献”的思想，考虑 $x \rightarrow y$ 中 $x$ 成为 $y$ 的儿子以后发生的事情，分别考虑 $f_{y,0}$ 和 $f_{y,1}$。 对于 $f_{y,0}$，它新增了 $\max\{f^*_{x,1}+z,f^*_{x,0}\}$（以下简称 $s^*(x)$）这一部分（$f^*$ 表示除去 $y$ 的贡献）；而对于 $f_{y,1}$，它内部的组成部分需要和 $s^*(x)$ 再次作比较（把这个组成部分抽出来有两种方法：（1）之前记录 $f_{y,1}$ 的时候就先不加上 $f_{y,0}$，要用的时候随用随加；（2）先减去 $f_{x,0}$，比较更新完再加回来）。 （下面默认采用第一种方法，修改 $f_{x,1}$ 的定义为原 $f_{x,1}-f_{x,0}$，即 $\max\{f_{y,0}-s(y)\}$。） 所以核心是找到 $f^*_{x,0}$ 和 $f^*_{x,1}$，即关键是如何除去 $f_x$ 中 $y$ 的贡献。 根据上面的转移方程，$f_{x,0}$ 是一个累加和，所以直接减去 $s(y)$ 就能得到 $f^*_{x,0}$；而 $f_{x,1}$ 是一个最大值，要想除去 $y$ 的贡献，根据上面那道题，也有两种方法（排序或记录次大值），于是成功得到了 $f^*_{x,1}$。 综上所述： $$f^*_{x,0}=f_{x,0}-s(y)$$ $$f^*_{x,1}=\left\{ \begin{array}{rcl} f_{x,1,1} & & {\textrm{if}\ f_{x,1,0}=f_{y,0}+z-s(y)}\\ f_{x,1,0} & & {\textrm{otherwise.}} \end{array} \right.$$ $$f'_{y,0}=f_{y,0}+s^*(x)$$ $$f'_{y,1}=\max\{f_{y,1},f^*_{x,0}-s^*(x)\}$$ 由上几题，$f'$ 和 $f$ 仍然可以压在一起，用一个数组储存，不再赘述。 答案即为 $\max\{f_{x,0}\}$。 #### 评价 一道正宗的纯正换根 DP 题，换根 DP 的常用技巧都囊括其中了，思维难度不低，代码和题面也不恶心人，也没有其它什么乱七八糟的算法喧宾夺主。 ### [CF1796E Colored Subgraphs](https://www.luogu.com.cn/problem/CF1796E) > 简化题意：给定一棵无根树，选择一个树根，构造一种树链剖分使最短的链最长。（只用输出这个最大值） 关键词：“无根树”，而且还要“选择一个最优的节点 $r$”，特征明显，试着往换根 DP 的方面去做。 首先需要求出以 $1$ 为根时，树链剖分使最短链的最大长度。 观察一棵树的结构可以发现，如果把叶节点视为树链开端，那么树链末端只会是根节点或者树上路径分叉的地方。从动态的角度思考，两条树链从叶节点开始延伸，在其 LCA 处会合，此时只能保留一条树链继续向上走，那么自然**优先选择短的那条**，否则这个子树上的答案就此确定为较短链长度，再无可能增大了。 #### 第一次 DP 对于一个节点，首先我们必须要知道所有以它的子节点为末端的树链长度。所以记 $F_x$ 表示以 $x$ 为末端的树链长度，那么根据上面的贪心策略，有（$x$ 为父节点，$y$ 为子节点）： $$F_x=\min\{F_y\}+1$$ 其次，别的未被选中继续延伸的树链也要纳入考虑。设 $G_x$ 表示 $x$ 的子树中没有继续延伸的最短树链长度，其由两个部分组成：所有子节点 $G$ 值的最小值和所有点 $F$ 值的**次小值**（最小值已经延伸出去了）。 $$G_x=\min( \operatorname{secmin}\{F_y\}, \min\{G_y\} )$$ （$\operatorname{secmin}$ 表示次小值） 最后以 $1$ 为根的答案就是 $\min\{F_x,G_x\}$。 #### 第二次 DP > 换根 DP 考虑的事情是很 Simple 的，就是合并子树外的信息，但是总会有一些讨厌的时候，现在恰好最优的东西刚好就在这个子树内，那我们就只能转移次要的转移点。——[吾王美如画](https://www.luogu.com.cn/user/118273) 本题中你将会遇到大量的这种情况。 按照惯例，换根 $DP$ 的转移方程中出现了最小值，那么就需要记录次小值。所以我们先将 $F$ 扩展成两层 $F_{x,0}$ 和 $F_{x,1}$，把 $G$ 也扩展成两层 $G_{x,0}$ 和 $G_{x,1}$，各自分别表示最小值和次小值。 然后我们就可以丢掉 $\operatorname{secmin}\{F_y\}$，它其实就是 $F_{x,1}$。 接着我们就会发现，转移的时候也同时**直接**需要次小值（而不仅仅是把它作为最小值的备用方案）。此时若 $y$ 恰好是 $F_{x,1}$ 的更新来源，**我们就还需要一个备用方案：次小值的次小值——即第三小值**，用 $F_{x,2}$ 表示。 对于换根 DP 来说上面的原始转移方程不是很好用，它不是一个纯 $\min$ 格式。所以我们需要一些新的状态和新的方程，用小写字母表示。 $F$ 方程中最后那个 $1$ 可以在用到它的时候加，而 $G$ 可以直接拆成两部分（其中一部分可以直接用 $F$ 表示），**两部分可以等到要用到时候再合并起来当作原来的 $G$ 计算**。 $f_{x,0/1/2}$ 表示**不加上 $x$ 本身**的最短/次短/第三短候选树链的长度，转移方程不变只是叶节点的值变为 $0$，有 $F_x=f_x+1$；$g_x$ 则表示以 $x$ 为根的子树中**不包括在 $x$ 处才断开的树链情况下**的最短链长度，那么 $G_x=\min(f_{x,1},g_x)$，它的转移方程可以由之前的方程略微修改得来： $$g_x=\min\{G_y\}=\min\{\min(f_{y,1},g_y)\}$$ 最后答案为 $\max\{\min(F_x,G_x)\}=\max\{\min(f_{x,0}+1,f_{x,1},g_x)\}

代码细节

这道题细节超多，但是只要记住这两条原则就行了：

总结

主要步骤

两次 DP 一般都采用 DFS 的方式（所以换根 DP 的代码里面通常都可以看到 DFS1 和 DFS2😁）

第二次 DP 的转移方程可以用两个思想考虑：

一般来说，简单或偏模板一点的题常用第一种思想，而较难的题用第二种思想更好解。

典型特征

准确来说，第一种特征属于第二种特征，只是问法更加直白，难度也会相应的较第二种更低。

可解条件

  1. 问题在确定根节点的情况下可解（第一次 DP）。
  2. 问题可进行换根转移（第二次 DP）。

条件 1 不属于换根 DP 的讨论范围，重点说条件 2：

根据【主要步骤】部分，换根 DP 第二次 DP 主要分为“消除该子节点对父节点的贡献”和“将这个父节点的贡献合并到子节点上”两个步骤。

既然第一次 DP 可以完成，即可以用子节点的答案合并出父节点的答案，那么第二步（额外合并一个贡献）一般都没有问题。核心是第一步（消除该子节点对父节点的贡献）。

首先，可逆的运算一定可以消除贡献，例如异或（异或消除）、加法（减法消除）、乘法（逆元或除法消除）。

其次，不可逆的运算部分一定程度上也能消除贡献，例如最值问题（通过记录次大次小值消除）。

最后，【例题 P3047】中提到的那种奇技淫巧似乎可以解决一切不可逆运算消除贡献的问题，这里整理归纳一下，过程如下：

  • 用 \otimes 表示某种合并运算，设 x 的子节点分别为 y_1,y_2,\dots,y_k。
  • 在第一次 DP 的时候记录这些子节点的前缀合并值 fl_i= f_{y_1} \otimes f_{y_2} \otimes \dots \otimes f_{y_i}、后缀合并值 fr_i= f_{y_i} \otimes f_{y_{i+1}} \otimes \dots \otimes f_{y_k}。
  • 在换根 DP 过程中记录由父亲转移过来的那部分答案 up_x，那么就有 up_{y_i}=fl_{i-1} \otimes fr_{i+1}，f'_{y_i}=f_{y_i} \otimes up_{y_i}。
  • 总体时间复杂度不变。

（不过这种方法依然要求满足结合律。）

其它细节

压缩状态

正常来说，推导换根 DP 状态转移方程的时候是需要将第一次 DP 的结果（记为 f_x）和第二次 DP 的结果（记为 ans_x）分开计算的，但是某些情况下，这两个可以合并到一起：

总体来说，大多数题目的 f 和 ans 都是可以压在一起计算的，即换根的时候可以直接在 f 上做修改。

注意事项

未来可能会再补充。

本文采用 「CC-BY-NC 4.0」 创作共享协议，转载请注明作者及出处，禁止商业使用。