树形dp总结

这类题型在 dp 中很常见，于是做一个总结吧！！！

最经典的题：没有上司的舞会

传送门：没有上司的舞会 - 洛谷

状态表示：

dp[i][0] 为 以 i 为根的子树中，选择 i 节点的最大欢乐值

dp[i][1] 为 以 i 为根的子树中，不选择 i 节点的最大欢乐值

状态转移方程  dp[i][0] += dp[[j][1]        dp[i][1] += dp[j][0]      j 为 i 的子节点

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 6e3 + 10;
int a[N];
int h[N], e[N], ne[N], idx;
bool flag[N] = { 0 };
int f[N][2];
void add(int a, int  b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}
void dfs(int u , int fa ) // 树形 dp 中一般都是用 dfs
{
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        dfs(j, u);
        f[u][0] += max(f[j][0] , f[j][1] );
        f[u][1] += f[j][0];
    }
}
void solve()
{
    memset(h, -1, sizeof h);
    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int i = 1; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        add(b, a);
        flag[a] = true;
    }
    int root = -1;

    for (int i = 1; i <= n; i++)
    {
        f[i][1] += a[i];
        if (!flag[i]) root = i;
    }

    dfs(root, -1 );

    
    cout << max (f[root][1], f[root][0]) << endl;
}
signed main()
{
    int tt = 1;

    while (tt--)solve();
    return 0;
}

再来一道经典题目：选课 （树形dp 点）

传送门：[CTSC1997] 选课 - 洛谷

状态表示：

dp[i][[j] 以 i 为根的子树中，选择 j 个节点的最大学分

状态转移方程：

 dp[i][j] = dp[i][j - k] + dp[t][k] （ t 为 j 的子节点 ，k 是从子树中选择 k 个节点 ）

注意：

1.你要统计子树中节点的个数

2. 需要假设一个虚拟源节点，因此要把 m++

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 620;
int f[N][N]; int n, m;
int h[N], e[N], ne[N], idx, score[N];
int Size[N];
void add(int a, int b)
{
    e[idx] = b; ne[idx] = h[a]; h[a] = idx++;
}
void dfs(int u, int fa)
{
    Size[u] += 1;
    f[u][1] += score[u];
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (j == fa)continue;
        dfs(j, u);
        Size[u] += Size[j];
        for (int t = min(m, Size[u]); t; t--) 
        // 注意 t 要从大到小遍历
        // 如果 t 要从小到大遍历，就会导致当 t 变大时，更新最新状态时，会用到这个子树刚刚更新的状态
        {
            for (int k = min(Size[j], t - 1); k >= 0; k--)
            {
                f[u][t] = max(f[u][t], f[u][t - k ] + f[j][k] );
            }
        }
    }
}
signed main()
{
    memset(h, -1, sizeof h);
    cin >> n >> m;
    m++;
    for (int i = 1; i <= n; i++)
    {
        int x; cin >> x; add(i, x); add(x, i);
        cin >> score[i];
    }

    dfs(0, -1);
    
    cout << f[0][m] << endl;
    return 0;
}

经典题目：二叉苹果树（树形dp 边）

传送门：https://www.luogu.com.cn/problem/P2015

状态表示：dp[i][j] 以 i 为根的子树中，保留 j 条边的最多苹果树

这道题有一个隐含的条件，当某条边被保留下来时，从根节点到这条边的路径上的所有边也都必须保留下来

状态转移方程：

dp[i][j] = max( dp[i][j] , dp[i][j-k-1] + dp[t][k] + w[i] ) （ t 为子节点，k是值子树中选择 k 条边）

注意这个题要统计子树中边的条数

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 220;
int f[N][N];
int h[N] , e[N] , ne[N] , idx , w[N];
int Size[N];
int n , m;
void add( int a , int b , int c )
{
    w[idx] =c ; e[idx] = b; ne[idx] = h[a] ; h[a] = idx++;
}
void dfs( int u , int fa )
{
    for( int i = h[u] ; i != -1 ; i = ne[i] )
    {
        int j = e[i];
        if( j == fa )continue;
        dfs( j , u );
        Size[u] += Size[j] + 1;
        for( int t = min( Size[u] , m ) ; t  ; t-- )
        {
            for( int k = min(Size[j] , t - 1 ) ; k >= 0 ; k-- )
            {
                f[u][t] = max( f[u][t] , f[u][t-k-1] + f[j][k] + w[i] );
            }
        }
    }
}
signed main()
{
    memset( h , -1 , sizeof h );
    cin >> n >> m;
    for( int i = 0 ; i < n - 1; i ++)
    {
        int a , b , c; cin>> a >> b >> c;
        add( a , b ,c  );add( b , a , c );
    }
    dfs( 1 , -1 );
    cout << f[1][m] << endl;
    return 0;
}