题解 | 最大学分

#include<bits/stdc++.h>
using namespace std;

const int N=400;

int f[N][N]; 
int n,m;
int ki[N],si[N];
vector<int> G[N];

int dfs(int u){
	int currents_nodes=1;
	for(int v:G[u]){
		int child_nodes=dfs(v);
		for(int i=min(m,currents_nodes);i>0;i--){
			for(int j=1;j<=min(child_nodes,m-i);j++){
				f[u][i+j]=max(f[u][i+j],f[u][i]+f[v][j]);
			}
		}
		currents_nodes+=child_nodes;
	}
	return currents_nodes;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>ki[i]>>si[i];
		f[i][1]=si[i];
		G[ki[i]].push_back(i);
	}
	m++;//虚拟化一个基础选修课 
	dfs(0);
	cout<<f[0][m]<<endl;
    return 0;
}