树形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;
}