题目大意
0v0在野外看到了一棵Galo树，看到食物的0v0瞪大了眼睛，变成了OvO。
这棵Galo树可以看做是一棵以$1$号点为根的$n$个点的有根数，除了根节点以外，每个节点$i$都有一个Galo，美味度为$w[i]$。
OvO发现，如果她摘下了$i$号Galo，那么$i$的子树中的Galo以及$i$到根的路径上的其他Galo都会死掉。
OvO的袋子只能装$k$个Galo，她的嘴巴里还能叼$1$个，请问她所摘Galo的美味度之和的最大值是多少？
题目分析
不难发现，题目求的是选出$k+1$个点，使得其任意一个点不是另一个点的祖先。
简单的树上背包。
设$f[i,j]$为在$i$的子树中分配$j$个点得到的最大美味值。
枚举儿子分配的值转移一下即可。
注意原本的转移是$O(nk^2)$的，根据$achen$讲过的以真实结点分配的树上背包是$O(n^2)$的。再优化一下，我们只需要分配所含有的叶子结点，故复杂度是$O(nk)$的。
代码
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
LL num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=100005,maxm=20000005;
int n,k,Size[maxn],id[maxn],a[maxn];
LL f[maxm],ans=0;
vector<int>edges[maxn];
void AddEdge(int x,int y) {
edges[x].push_back(y);
}
int min(int x,int y) {
if(x<y)return x;
return y;
}
LL max(LL x,LL y) {
if(x>y)return x;
return y;
}
void TreeDp(int Now) {
if(!edges[Now].size())Size[Now]=1;
for(int Next:edges[Now]) {
TreeDp(Next);
Size[Now]+=Size[Next];
for(int i=min(Size[Now],k); i>=0; i--)
for(int j=min(Size[Next],i); j>=0; j--)
f[id[Now]+i]=max(f[id[Now]+i],f[id[Now]+i-j]+f[id[Next]+j]);
}
f[id[Now]+1]=max(f[id[Now]+1],a[Now]);
}
int main() {
n=Get_Int();
k=Get_Int()+1;
for(int i=2; i<=n; i++) {
int x=Get_Int();
AddEdge(x,i);
a[i]=Get_Int();
id[i]=(i-1)*(k+1);
}
TreeDp(1);
for(int i=0; i<=k; i++)ans=max(ans,f[i]);
printf("%lld\n",ans);
return 0;
}
|
