AcWing 286. 选课
原题链接
中等
作者:
lwyznoip
,
2023-10-01 18:38:44
,
所有人可见
,
阅读 65
#include <bits/stdc++.h>
using namespace std;
const int N = 310;
int n, m;
int h[N], e[N], ne[N], idx;
int f[N][N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int dfs(int u) //返回以 u 为根的节点数量
{
int num = 1;
for (int i = h[u]; ~i; i = ne[i])
{
int v = e[i];
int t = dfs(v);
num += t;
for (int j = num; j; j--) // j 应该从当前以 u 为根的子树遍历过的节点开始枚举
for (int k = 0; k < j && k <= t; k++) //以 v 为根的子树分得的节点数应该小于其子树的总结点数 t
f[u][j] = max(f[u][j], f[u][j - k] + f[v][k]);
}
return num;
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
for (int i = 1; i <= n; i++)
{
int p;
cin >> p >> f[i][1];
add(p, i);
}
dfs(0);
cout << f[0][m + 1];
return 0;
}