DP总结(二，树形DP)

0.定义

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

1.转移方式

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

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

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

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

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

2.类型 & 例题

1.朴素版本

Eg.1 最大子树和↗

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

所以，有 DP 方程：

dp _ u = \sum _ {v \in son(u)} max\{dp _ v,0\}

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

代码实现↗

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

填了 24.11.19 背包 DP 的坑

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

1
void DP(int u,int fa)
2
{
3
    for(auto v:g[u])
4
    {
5
        if(v == fa)
6
            continue;
7
        DP(v,u);
8
        for(int j = m;j >= 0;j--)
9
        {
10
            for(int k = 0;k <= j;k++)
11
                dp[u][j] = max(dp[u][j],dp[u][j - k] + dp[v][k] + val);
12
        }
13
    }
14
}

上述代码中， $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
void DP(int u,int fa)
2
{
3
    for(auto x:g[u])
4
    {
5
        int v = x.first;
6
        if(v == fa)
7
            continue;
8
        DP(v,u);
9
        for(int j = m;j >= 1;j--)
10
        {
11
            for(int k = 0;k < j;k++)
12
                dp[u][j] = max(dp[u][j],dp[u][j - k - 1] + dp[v][k] + x.second);
13
        }
14
    }
15
}