DP总结(二，树形DP)

0.定义#

顾名思义就是在树上的 DP。

1.转移方式#

这种 DP 不能用普通的方式转移，一般是通过 DFS 来实现转移，因为他的状态转移方程一般和子节点有关，所以可以计算完子节点的答案后合并到父节点。

一般来说，答案是根节点的答案

但是，这个树不一定是有根树

所以有些时候得扫一遍，求出以每个节点为根的答案。

题型很多，基本可以和其他任何一种 DP 融合起来。

2.类型 & 例题#

1.朴素版本#

Eg.1 最大子树和

一看就是树形 DP （放在这那不是废话吗）

对于一条边，有两种决策：保留或者计入子树答案

所以，有 DP 方程：

意思就是，看是否保留子树的答案，如果子树答案小于 $0$，则一定劣于不选该子树，所以可以这么写。

代码实现

2.树上背包（有依赖的背包）#

填了 24.11.19 背包 DP 的坑

其实就是在树上的分组背包，模板如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14

void DP(int u,int fa)
{
    for(auto v:g[u])
    {
        if(v == fa)
            continue;
        DP(v,u);
        for(int j = m;j >= 0;j--)
        {
            for(int k = 0;k <= j;k++)
                dp[u][j] = max(dp[u][j],dp[u][j - k] + dp[v][k] + val);
        }
    }
}

上述代码中，$j$ 表示给以这个节点为根的子树分配多少容量，$k$ 表示给该节点的子节点为根的子树分配多少容量。

Eg.2 二叉苹果树

可以选子树中的边的充分条件是选择该条边，所以说上面的 $j$ 只能遍历到 $1$。同时，转移方程为 $dp _ {u,j} = max(dp _ {u,j},dp _ {u,j - k - 1} + dp _ {v,k} + w _ {u \to v})$。

所以 DP 转移代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

void DP(int u,int fa)
{
    for(auto x:g[u])
    {
        int v = x.first;
        if(v == fa)
            continue;
        DP(v,u);
        for(int j = m;j >= 1;j--)
        {
            for(int k = 0;k < j;k++)
                dp[u][j] = max(dp[u][j],dp[u][j - k - 1] + dp[v][k] + x.second);
        }
    }
}

代码实现

3.换根DP#

就是根节点的修改会导致一些变化。

Eg.3 STA-Station

首先，我们需要一遍 DFS 来处理子树大小。

然后，令 $dp _ u$ 为当以 $u$ 为根时，节点的深度和。

所以，有 DP 方程:

因为:

1. 在 $v$ 的子树上的节点深度减少 $1$，深度和减少了 $size _ v$
2. 不在 $v$ 的子树上的节点深度增加了 $1$，则深度和减少了 $n - size _ v$

所以最后再扫一一遍就可以求出答案了。

代码实现

我觉得就差不多了