[学习笔记]换根dp

0 前言

换根dp应该是树形dp中比较难理解的一类dp了

当然，理解了之后就没有难度了

1 引入

我们来看这个题

给出一个 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)

为啥打上了括号呢？是因为这样更好理解了

如果看不懂，我来解释一下

$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) 的时间内搞定啦

还有什么不懂的地方我们稍微放一点核心代码吧

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

这题和上面那题就非常类似了，只是点和边都加上了权值

理解上面那题这题就不难理解了

【例题2】Nearby Cows

也是一道挺简单的换根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

一道比较烦的换根dp

分类讨论其实很烦，若要看这题完整的解法，可以看我这篇题解

这里我们令 g_u 为以 u 为根的子树中从 u 开始把所有家在这个子树内的人送回家并回到 u 节点的最短路程

接下来，由于车子出发之后不一定要回到原来的出发点，所以要统计最长链和次长链，接下来再来一次dfs合并答案即可

【例题4】连珠线

一道比较难的换根dp，也是只提思路

我们令 f_{u,0/1} 为 u 节点是/不是蓝线中点的答案

接下来，令 g_{u,0/1,v} 为 u 节点是/不是蓝线中点的不考虑 v 这个儿子的答案

记录一下不考虑每个儿子的最大值，然后合并一下答案就行了

还要看具体的做法可以看题解

4 结尾

换根dp确实是一种难理解的树形dp，但是很多题目都要用到这个技巧，所以必须要学啊