摘要:树上的贪心问题

「HEOI2015」兔子与樱花

题面

题目分析

这个思路有点怪?

首先我们发现删除一个点的性质,假设这个点的删除是最优的情况,也就是在承重范围内删去了尽量多的点并且承重最小,那么它对于父亲节点来说也具有最优性.

其实很显然,在删除节点一样的情况下,尽量地让承重小一定是最优的,又因为一个点的儿子节点的删除对这个点的父亲节点仅会使得以后可能的儿子节点变小(就是删除了之后拼上来的儿子),所以尽量要在儿子节点上能删多少就删多少并最优,不然等于浪费了当前剩余的承重.

还得记录一个值,就是每个节点处理完之后剩下的儿子数,在它的父亲的删除中要考虑上这些之后会拼上来的儿子.

然后按照儿子节点的樱花数量加上剩下的儿子进行排序,能取多少取多少,并更新当前点的樱花数量和剩下的儿子数.

代码

洛谷上的空间128mb貌似给小了,bzoj和loj都是256mb(应该就是原题限制了),导致此做法loj和bzoj可过但洛谷上mle一个点,于是用时间换了下空间,开了编译优化.

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O2")
#pragma GCC optimize("inline")
#include "iostream"
#include "cstdlib"
#include "cstdio"
#include "cstring"
#include "cmath"
#include "cctype"
#include "ctime"
#include "iomanip"
#include "algorithm"
#include "set"
#include "queue"
#include "map"
#include "stack"
#include "deque"
#include "vector"
#define R register
#define INF 0x3f3f3f3f
#define debug(x) printf("debug:%lld\n",x)
#define debugi(x) printf("debug:%d\n",x)
#define debugf(x) printf("debug:%llf\n",x)
#define endl putchar('\n')
typedef long long lxl;
const lxl big=2000010;
lxl n,m,EdgeSize;
lxl head[big],f[big],val[big],size[big],ext[big];
struct _Edge
{
lxl v,next;
}e[big<<1];
inline lxl read()
{
char c(getchar());
lxl f(1),x(0);
for(;!isdigit(c);(c=='-')&&(f=-1),c=getchar());
for(;isdigit(c);x=(x<<1)+(x<<3)+(c^48),c=getchar());
return f*x;
}
#define add(u,v) EdgeAdd(u,v),EdgeAdd(v,u)
inline void EdgeAdd(lxl u,lxl v)
{
e[EdgeSize].v=v;
e[EdgeSize].next=head[u];
head[u]=EdgeSize++;
}
inline bool cmp(lxl d1,lxl d2)
{
return val[d1]+ext[d1]<val[d2]+ext[d2];
}
void dfs(lxl u,lxl fa)
{
lxl g(0);
std::vector<lxl>rom;
size[u]=1;
for(R int i(head[u]);~i;i=e[i].next)
{
lxl v=e[i].v;
if(v==fa)continue;
dfs(v,u);
size[u]+=size[v],f[u]+=f[v],++g;
rom.push_back(v);
}
g+=val[u];
std::sort(rom.begin(),rom.end(),cmp);
auto it=rom.begin();
for(;it!=rom.end();++it)
{
lxl v=*it;
lxl add=ext[v]+val[v]-1;
if(g+add<=m)
g+=add,++f[u],val[u]+=val[v],ext[u]+=ext[v];
else break;
}
for(;it!=rom.end();++it)++ext[u];
}
int main(void)
{
memset(head,-1,sizeof head);
n=read(),m=read();
for(R int i(1);i<=n;++i)val[i]=read();
for(R int i(1);i<=n;++i)
{
lxl k=read();
for(R int j(1);j<=k;++j){lxl x=read()+1;add(i,x);}
}
dfs(1,0);
printf("%lld\n",f[1]);
return 0;
}