题解
树形背包板子题。
设$f[i][j]$表示在以$x$为根的子树选$j$门课（包括$x$）能够获得的最高学分，用分组背包转移即可。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| #include<cstdio>
#include<vector>
#define RG register
inline int read()
{
int data = 0, w = 1;
char ch = getchar();
while(ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
if(ch == '-') w = -1, ch = getchar();
while(ch >= '0' && ch <= '9') data = data * 10 + (ch ^ 48), ch = getchar();
return data*w;
}
const int maxn(310);
std::vector<int> g[maxn];
typedef std::vector<int>::iterator iter;
int s[maxn], f[maxn][maxn], n, m;
void dfs(int x)
{
f[x][0] = 0;
for(RG iter it = g[x].begin(); it != g[x].end(); ++it)
{
int to = *it; dfs(to);
for(RG int v = m + 1; v; --v)
for(RG int j = 0; j < v; ++j)
f[x][v] = std::max(f[x][v], f[x][v - j] + f[to][j]);
}
}
int main()
{
n = read(); m = read();
for(RG int i = 1; i <= n; i++)
g[read()].push_back(i), f[i][1] = s[i] = read();
dfs(0); printf("%d\n", f[0][m + 1]);
return 0;
}
|