[学习笔记]换根dp

### 0 前言 换根dp应该是树形dp中比较难理解的一类dp了 ~~当然，理解了之后就没有难度了~~ ### 1 引入 我们来看[这个题](https://www.luogu.com.cn/problem/P3478) >给出一个 N 个点的树,找出一个点来,以这个点为根的树时,所有点的深度之和最大 我们先来看看 $\Theta(n^2)$ 的暴力怎么做吧 我们珂以枚举每一个点，将其作为根，然后求出每一个点的深度然后统计深度和就行了 再一看数据范围 $n\le 10^6$，显然无法通过 那么，我们应该如何来优化呢？ ### 2 换根dp 我们可以利用一些技巧来把这一类问题优化到 $\Theta(n)$ 的时间内解决 接下来，我们就要引入换根dp的一些思想 ~~（或者叫套路）~~ 了 换根dp一般分为三个步骤 1、先指定一个根节点 2、一次dfs统计子树内的节点对当前节点的贡献 3、一次dfs统计父亲节点对当前节点的贡献并合并统计最终答案 光这么说可能不太好理解，我们来结合上面的那个例子看看吧 我们先来看一个节点 $u$ 的子树里面的节点对它的贡献： 很明显，这个贡献就是子树里所有节点到 $u$ 的深度和，我们把它记为 $g_u$ （不过待会会发现根本不需要这个 $g_u$） 接着，我们记 $sz_u$ 为以 $u$ 为根的子树大小，$dep_u$ 为点 $u$ 到 1 号节点（我们指定的根节点）的深度（之后有用） 接下来，我们来考虑第2次dfs，也就是计算父亲对它的贡献 我们令 $f_u$ 为以 $u $ 为根节点的深度和 所以，我们令 $v$ 为 $u$ 的一个儿子节点，可得 $f_v=g_v+(f_u-(g_v+sz_v))+(sz_1-sz_v)$ 为啥打上了括号呢？是因为这样更好理解了 如果看不懂，我来解释一下 $g_v$ 是以 $v$ 为根的子树深度和，显然要加上 $f_u$ 是父亲 $u$ 节点的答案，显然要减去我们 $v$ 子树里的信息（不然就多算了） 那么，$g_v+sz_v$ 就是我们 $v$ 子树的信息了 有人就要问了，子树里的的信息不就是 $g_v$ 吗？ 但是我们是从父亲的答案减去，显然在以 $u$ 为根时，$v$ 的子树中的所有节点的深度都有加一，于是就增加 $sz_v$ 同理，后面的 $sz_1-sz_v$ 就是非 $v$ 节点子树中的点啦，和上面一样理解一下就好啦qwq 解释完了，我们化简一下这个柿子 $f_v=f_u+sz_1-2\times sz_v$ 发现可以不用记录 $g$ 于是，我们就可以在 $\Theta(n)$ 的时间内搞定啦 还有什么不懂的地方我们稍微放一点核心代码吧 ```cpp void dp1(int u,int fa) { sz[u]=1; for(int i=Head[u];i;i=Edge[i].next) { int v=Edge[i].to; if(v==fa)continue; dep[v]=dep[u]+1;//深度 dp1(v,u); sz[u]+=sz[v];//子树大小 } } void dp2(int u,int fa) { for(int i=Head[u];i;i=Edge[i].next) { int v=Edge[i].to; if(v==fa)continue; f[v]=f[u]-2*sz[v]+sz[1];//转移方程 dp2(v,u); } } in main: dp1(1,0); for(int i=1;i<=n;i++)f[1]+=dep[i];//计算1号节点的答案 dp2(1,0); int ans=-19260817,id=0; for(int i=1;i<=n;i++) if(ans<f[i])ans=f[i],id=i;//统计最终的答案 ``` ### 3 总结&例题 总结一下，换根dp主要是用来解决树上根不确定的时候的dp问题，通常可以将 $\Theta(n^2)$ 的暴力统计做到 $\Theta(n)$ 的dp 换根dp一共分成3步： 1、选择一个节点作为根 2、统计子树内节点对它的贡献 3、统计父亲节点对它的贡献并计算最终答案 理解了这些步骤，我们就可以来~~切~~做几道题啦 【例题1】[Great Cow Gathering](https://www.luogu.com.cn/problem/P2986) 这题和上面那题就非常类似了，只是点和边都加上了权值 理解上面那题这题就不难理解了 【例题2】[Nearby Cows](https://www.luogu.com.cn/problem/P3047) 也是一道挺简单的换根dp题 我们令 $f_{u,k}$ 为以 $u$ 为根，距离 $u$ 为 $k$ 的节点权值和 也是先计算 $u$ 的子树对 $u$ 的贡献，$f_{u,k}=\sum f_{v,k-1}$，$v$ 为 $u$ 的子节点 接下来，我们计算父亲节点对它的贡献，$f_{u,k}=f_{u,k}+ f_{fa,k-1}$，其中，$fa$ 为 $u$ 的父亲 最后，我们还要去重 ~~（留给读者自行思考，并不难想）~~ 总时间复杂度 $\Theta(nk)$ 【例题3】[Kamp](https://www.luogu.com.cn/problem/P6419) 一道比较烦的换根dp 分类讨论其实很烦，若要看这题完整的解法，可以看我[这篇题解](https://sflsrick.blog.luogu.org/solution-p5898) 这里我们令 $g_u$ 为以 $u$ 为根的子树中从 $u$ 开始把所有家在这个子树内的人送回家并回到 $u$ 节点的最短路程 接下来，由于车子出发之后不一定要回到原来的出发点，所以要统计最长链和次长链，接下来再来一次dfs合并答案即可 【例题4】[连珠线](https://www.luogu.com.cn/problem/P3647) 一道比较难的换根dp，也是只提思路 我们令 $f_{u,0/1}$ 为 $u$ 节点是/不是蓝线中点的答案 接下来，令 $g_{u,0/1,v}$ 为 $u$ 节点是/不是蓝线中点的不考虑 $v$ 这个儿子的答案 记录一下不考虑每个儿子的最大值，然后合并一下答案就行了 ~~还要看具体的做法可以看题解~~ ### 4 结尾 换根dp确实是一种难理解的树形dp，但是很多题目都要用到这个技巧，~~所以必须要学啊~~