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)$ )

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

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

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

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

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，但是很多题目都要用到这个技巧，所以必须要学啊