「Luogu1552」[APIO2012]派遣

最近状态都不是很好,写完这个题感觉手感好像恢复了一些


problem

Solution

这个数据范围显然树形DP是做不了的

我们考虑,在预算范围内,选中的忍者越多越好,那么我们在一棵子树中选中的忍者一定是薪水最少的若干个

对每个节点维护一个大根堆,并记录每个堆的大小和堆中元素的权值和

考虑一棵子树时,用类似树形DP的方法将所有儿子合并到根

如果堆中元素权值和大于预算,不断弹出堆顶直到权值和不大于预算即可

最后对子树进行统计,更新答案

可并堆可以用左偏树实现

另外,还需要记录每个节点对应的左偏树的根的编号

Code

一开始没开long long还wa了一发

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
93
94
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
typedef long long ll;

template <typename T>void read(T &t)
{
t=0;int f=0;char c=getchar();
while(!isdigit(c)){f|=c=='-';c=getchar();}
while(isdigit(c)){t=t*10+c-'0';c=getchar();}
if(f)t=-t;
}

const int maxn=100000+5;
int n,root;
ll m;
ll mng[maxn];
ll ans;

struct edge
{
int u,v,nxt;
}g[maxn];

int head[maxn],ecnt;
void eADD(int u,int v)
{
g[++ecnt].u=u;
g[ecnt].v=v;
g[ecnt].nxt=head[u];
head[u]=ecnt;
}

int rec[maxn];
struct node
{
int ls,rs,dist;
ll val,siz,sum;
}mxh[maxn];

int Merge(int x,int y)
{
if(!x || !y)return x+y;
if(mxh[x].val<mxh[y].val)swap(x,y);
mxh[x].rs=Merge(mxh[x].rs,y);
if(mxh[mxh[x].ls].dist<mxh[mxh[x].rs].dist)
swap(mxh[x].ls,mxh[x].rs);
mxh[x].dist=mxh[mxh[x].rs].dist+1;
mxh[x].siz=mxh[mxh[x].ls].siz+mxh[mxh[x].rs].siz+1;
mxh[x].sum=mxh[mxh[x].ls].sum+mxh[mxh[x].rs].sum+mxh[x].val;
return x;
}

int Pop(int x)
{
int ls=mxh[x].ls,rs=mxh[x].rs;
return Merge(ls,rs);
}

void dfs(int u)
{
for(register int i=head[u];i;i=g[i].nxt)
{
int v=g[i].v;
dfs(v);
rec[u]=Merge(rec[u],rec[v]);
}
while(mxh[rec[u]].sum>m && mxh[rec[u]].siz)
rec[u]=Pop(rec[u]);
ans=max(ans,1ll*mxh[rec[u]].siz*mng[u]);
}

int main()
{
read(n),read(m);
for(register int i=1;i<=n;++i)
{
int u;
read(u),read(mxh[i].val),read(mng[i]);
mxh[i].sum=mxh[i].val;
mxh[i].siz=1;
rec[i]=i;
if(u)eADD(u,i);
else root=i;
}
dfs(root);
printf("%lld",ans);
return 0;
}