题目链接
https://www.luogu.com.cn/problem/P2014
思路
首先,我们发现,如果0算一个节点的话,整张图就是一棵树。
显然,父节点的信息可以由子节点合并得到并且不会影响子节点。
因此,我们定义 d p u , i , j dp_{u,i,j} dpu,i,j表示节点 u u u的前 i i i个子节点,背包容量为 j j j时可以获得的最大学分。
因此本题转化成了经典的01背包问题。
代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 3e2 + 5;
int n, m;
int dp[N][N];
vector<int>mp[N];
void dfs(int u)
{for (int j : mp[u]){dfs(j);}for (int i : mp[u]){for (int j = m; j >= 0; j--){for (int k = 0; k < j; k++){dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[i][k]);}}}
}
void solve()
{cin >> n >> m;m++;for (int i = 1, k, s; i <= n; i++){cin >> k >> s;mp[k].push_back(i);dp[i][1] = s;}dfs(0);cout << dp[0][m] << endl;
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int test = 1;// cin >> test;for (int i = 1; i <= test; i++){solve();}return 0;
}