树形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 点）
状态表示：
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;
}原文地址：https://blog.csdn.net/wx20041102/article/details/143750349
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！