想不到什么骚话了，就放一个Alice在这里吧(我gif去哪了)

树形$DP$是一种基于树形结构求解问题的动态规划形式，它一般以子树为状态，在$DFS$遍历整颗树的时候同时从子节点向父节点转移，最终得出全局最优解

最基础的树形$DP$就是我们在背包篇讲到的树形(依赖)背包，不知道的读者可以自行阅读，这里就不在赘述解决方式

从这道题可以看出树形$DP$一般以"以root为根的子树"作为一维，因为这样子便于我们定位节点并且不会出现重复计算的错误

在进行$DFS$的过程中，根据推到出来的转移方程进行转移便可求解

你可能想："哎主包主包，这个树形$DP$怎么这么$rt$"，别急，阴的还在后面呢

---

换根DP

作为树形$DP$的一个分支，换根$DP$阴的要命十分有意思，它通过增加维数或记录额外信息等方式，可以做到在$DP$过程中更换根节点的效果

例题+代码：「POI2008」STA-Station

void preperation( int p,int fa )//先预处理出每个节点的深度以及以它为根的子树大小，f[i]此时与siz[i]相等
{
    siz[p]=1, f[p]=siz[p];//初始化
    for( auto x:rode[p] )//枚举子节点
    {
        if( x == fa ) continue;//不能由子至父
        dep[x]=dep[p]+1;//更新深度
        preperation( x,p );//继续递归
        siz[p]+=siz[x];//更新siz
        f[p]+=f[x];//更新f[i]
    }
}

void dfs( int p,int fa )//二次DFS求解答案
{
    if( f[ans] < f[p] || ( f[ans] == f[p] && ans > p ) ) ans=p;//答案更优
    for( auto x:rode[p] )//枚举子节点
    {
        if( x == fa ) continue;//不能由子至父
        f[x]=f[p]+n-2ll*siz[x];//换根DP
        dfs( x,p );//继续递归
    }
}

看不懂是吧，能一下看懂你就是甜菜了，这里我放一个图便于大家理解

正方形表示省略的子树，我们现在考虑从节点$1$转移到节点$2$它的总深度的变化是怎样的

首先，对于$2$所在的子树，它们相对于新根的距离全部减少了一，总共就是$siz[2]$

其次，对于$2$所在的子树以外的部分，它们相对于新根的距离全部增加了一，总共就是$n-siz[2]$

所以节点$2$的答案就可以得到了：$f[2]=f[1]-siz[2]+n-siz[2]$

那么对于节点$p$与其子节点$x$，则$f[u]=f[p]-siz[x]+n-siz[x]$

我们只需要找最大的$f[u]对应的u$就可以解决这道题了、

总的来说，换根$DP$最主要的部分在于考虑如何记录额外信息以完成换根的目的