树形dp和他的一些板子介绍

说来惭愧，我到现在还不会树形 DP……

树形 DP 是什么？

他就是一种 DP，只不过是搬到了树上。求解树上一个点的答案可以从他的儿子们 DP 转移过来时，那么使用树形 DP 是可行的。

树形 DP 一般是首先 DFS 到叶子节点，然后再从叶子节点一层层递归上来，得到答案。

而树形 DP 的最大难点就是如何设状态和转移方程。

那我们先来看几道例题来入门树形 DP。

P2015

树上背包。

容易发现这棵树如果是一个链的话，那么就非常好 DP。但是他现在是在树上。怎么设状态呢？

我们设为点保留条边时的答案。容易发现最终答案就是。然后状态设出来之后，就开始考虑转移方程。

每一个点是怎么转移过来的？想象一个点，他有一堆儿子，求解一个点的最终答案就相当于是在一堆儿子里面分配边数：第一个儿子留多少条边，第二个儿子留多少条边，然后一直这样下去。

这样我们就可以一个儿子一个儿子的转移：遍历儿子，然后转移这个式子：

$dp_{x, j} = \max(dp_{x, j}, dp_{x, j-k-1}+ dp_{v, k} + Edge_{x \rightarrow v}.val)$

用代码就这样表示：

for(int i=h[x];i;i=edge[i].nxt){
    int v = edge[i].to;
    if(v==father) continue;
    dfs(v, x);
    siz[x] += siz[v] + 1;
    for(int j=min(q, siz[x]);j>=0;j--){
        for(int k=0;k<=min(j-1, siz[v]);k++){
            dp[x][j] = max(dp[x][j], dp[x][j-k-1] + dp[v][k] + edge[i].w);
        }
    }
}

这里解释一下：是之前选了条边，是这个儿子选了条边。因为从这个点到他的儿子要条边，所以之前的就是条。然后就是这个从到的树枝上有多少个苹果。

这里优化了一下：

的范围变成了，因为这一个状态是基于前一个状态，而这个玩意只有二维，所以必须倒序遍历，以防重复选中。
的范围变成了，因为是之前的加上现在选的一共条边。然后从极端条件上来看，边全选这个儿子的，又因为从这个点到他的儿子连了一条边，所以就只能选条边。并且你还要考虑到儿子的子树的边数，所以要取 min。

总体代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 103;
struct Edge{
    int to, nxt, w;
}edge[N<<1];
int h[N], cnt;
void _add(int x, int v, int w){
    edge[++cnt] = {v, h[x], w};
    h[x] = cnt;
}
void add(int x, int v, int w){
    _add(x, v, w), _add(v, x, w);
}
int siz[N], n, q;
int dp[N][N];
void dfs(int x, int father){
    for(int i=h[x];i;i=edge[i].nxt){
        int v = edge[i].to;
        if(v==father) continue;
        dfs(v, x);
        siz[x] += siz[v] + 1;
        for(int j=min(q, siz[x]);j>=0;j--){
            for(int k=0;k<=min(j-1, siz[v]);k++){
                dp[x][j] = max(dp[x][j], dp[x][j-k-1] + dp[v][k] + edge[i].w);
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin>>n>>q;
    int u, v, w;
    for(int i=1;i<n;i++){
        cin>>u>>v>>w;
        add(u, v, w);
    }
    dfs(1, 0);
    cout<<dp[1][q];
    return 0;
}

P1352

这个也是树形 DP，这个的 DP 状态非常好设，就是设就是不选点的目前的最大权值，是选了点的目前的最大权值。

第二维为就是不选该点，那么他的儿子可以选也可以不选，就在这两个状态里取 max。
第二维为就是选了该点，那么他的儿子只能不选，就直接等于。

但是因为一个点有多个儿子，所以这个状态的值就是每一个儿子的答案加起来。

最后取即可。

P.S. 这道题其实就是求「最大权值独立集」的权值。从题意就可以看出来。所以实际上，不需要求根。随便选一个根都可以求出答案。

P2016

和上一道题思路相似。

设为点目前没放士兵的答案，为点目前放了士兵的答案。

如果当前点没有放士兵，那么他的儿子必须全部放士兵，否则这个点到这个点的儿子的这条边就会没有被观测。所以。
如果当前点放了士兵，那么他的儿子有没有放士兵就不用管了。所以。

然后因为所有点都可以变成根，所以 DFS 完了之后直接输出（rt随便设然后 DFS）即可。

P2014

这道题还是用树形 DP 的那些套路：这个也是树上背包。

设为包含点的子树要选个点的最大值。

这个就默认的是这个必选，所以循环的时候就要写到 i>=2 就行了。

这个的转移方程和之前的也很像：

$\begin{equation} \left\{ \begin{aligned} %\nonumber dp_{x, i} &= s_x &(i = 1)\\ dp_{x, i} &= \max_{v \in son_x}(dp_{x, i-j} + dp_{v, j}) &(2\le i \le siz_x)\\ \end{aligned} \right. \end{equation}$

P1273

这道题也是一个树形 DP，转移方式和之前相似。看了前面几道题应该就会转移了。

只需注意几个点：

将 memset 为负无穷大。
再把设为，因为不选就是。
然后算答案就把人数从大到小枚举，如果，就直接输出即可。

P1272

这道题的树形 DP 比较不容易发现：

我们和之前一样，设为目前以为根的子树拆出个节点的子树的所需切断道路的数目。

然后可以像之前一样得出转移方程：

$\begin{equation} \left\{ \begin{aligned} %\nonumber dp_{x, i} &= 0 &(i = 1 并且在循环外)\\ dp_{x, i} &= \max_{v \in son_x}(dp_{x, i} + 1, dp_{x, i-j} + dp_{v, j}) &(1\le i \le siz_x)\\ \end{aligned} \right. \end{equation}$

注意到这里的 +1。

因为你枚举点的一个儿子，你要把上一个儿子的状态转移到这个儿子的状态，有一种选择就是把连接的边给切掉。这样你就又收获了一棵大小为的子树了！

然后另一种就是之前的儿子加上根节点留个点，这个儿子加上他的子树留个点，这样就一共个点了！

为什么并且在循环外？因为在遍历儿子之前，你可以直接发现目前只有一个点的树。所以你甚至可以不用切就得到了目前大小为的一棵树，但是遍历儿子的时候会更改这个值，所以不用担心。

也是：注意 memset 初始值！！！

P1453

这道题要把环转化成树。

我们用并查集来维护连通块。如果有环的话就会在加点前就会发现。

因为最开始这个环显而易见的，是一条链。而当这条链首尾相连时，就会变为环。所以在加点前，判一下如果 find(u) == find(v)，那就说明成环了，然后就可以拆环了。

拆环，就相当于是只要上面那个条件成立，那么就不加这条边。设这个时候的为，为，这个问题就被转化成了：

给定一棵树，这棵树的点和点不能同时选，相邻的两个点不能同时选，求选出来的数的最大权值和。

是不是很熟悉？这就是ext-P1352！！！求最大权值独立集的权值。

不过这道题要转化一下：

因为点和点不能同时选，那就先不选，以为根跑一遍 DFS，记不选的答案为；再不选，以为根跑一遍 DFS，记不选的答案为。最后求，再乘上题目给的系数，即可。