树形依赖背包。
树上分组背包
树形DP常规思路
f[i][j].i为阶段，指以i为根的子树，状态j时的情况。
这一题 ，F[i][j]，以i为根的子树，选j门课，所得的最大学分。
转移：
相当于要在子树中选择j-1门课（因为必须选i才能选其子节点），使得学分最大。
这类问题可以转化为分组背包来做：
设i的子树有x个。
在x组中选体积j-1的物品（把课的个数转化为体积），每组至多选一个，每组有j-1个物品，物品的体积是1 -- j-1
因为每个儿子节点必须先选了才能选他的儿子节点。第i个儿子节点选k个相当于，选了体积为k的物品，价值为f[i][k].
然后直接转移即可
#include <bits/stdc++.h> using namespace std; typedef long long ll; //typedef __int128 LL; //typedef unsigned long long ull; //#define F first //#define S second typedef long double ld; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef pair<ld,ld> pdd; const ld PI=acos(-1); const ld eps=1e-9; //unordered_map<int,int>mp; #define ls (o<<1) #define rs (o<<1|1) #define pb push_back const int seed=131; const int M = 1e4+7; struct node { int nxt,to; }ee[M]; int cnt,head[M]; void add(int u,int v) { ee[++cnt].to=v; ee[cnt].nxt=head[u]; head[u]=cnt; } int du[M], s[M]; int n,m; int f[M][M];//以i节点为根的子树，选择j个 学科 得到的最大分数 void dfs(int u) { f[u][0]=0; //cout<<u<<endl; for(int i=head[u];i;i=ee[i].nxt)//分组背包 对应组数 { int v=ee[i].to; dfs(v); for(int j=m;j>=1;j--)//分组背包体积 for(int k=1;k<=j;k++)//分组背包 每组的个数 { if(j>=k) f[u][j]=max(f[u][j],f[u][j-k]+f[v][k]); } } if(u!=0) for(int i=m;i>=1;i--) f[u][i]=f[u][i-1]+s[u]; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin>>n>>m; for(int i=1;i<=n;i++) { int x,y; cin>>x>>y;s[i]=y; add(x,i);du[i]++; } for(int i=1;i<=n;i++)if(du[i]==0)add(0,i); dfs(0); cout<<f[0][m]<<endl; return 0; }
