【可并堆】派遣

可并堆

传送门：CodeVS1763

做法比较显然，就是给每一个点建一个堆，然后统计以该点为管理者的最优答案，更新一下，然后把这个堆合并到他的父亲节点上，有点类似树形Dp

注意的是建大根堆似乎更优（小根堆秒了的请无视）

统计大根堆里元素之和，然后和预算比较一下，超了就弹出最大的，更新元素和，直到没超为止，更新答案。然后把堆里余下的直接合并到父亲节点即可（因为已弹出的合并了也用不上）

以下代码（左偏树实现）：

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
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define LL long long
LL n,m,ans,tot;
LL h[300030],ls[300030],rs[300030],dist[300030];
LL root[100030],s[100030],ss[100030],a[100030],c[100030],l[100030],head[100030];
struct edge{
	LL v,next;
}e[100030];
void add(LL x,LL y){
	tot++;
	e[tot].v=y;
	e[tot].next=head[x];
	head[x]=tot;
}
int merge(LL x,LL y){
	if (!x || !y) return x|y;
	if (h[x]<h[y]) swap(x,y);
	rs[x]=merge(rs[x],y);
	if (dist[ls[x]]<dist[rs[x]]) swap(ls[x],rs[x]);
	dist[x]=dist[rs[x]]==0?dist[rs[x]]+1:0;
	return x;
}
	
void search(int x){
	for (int i=head[x];i;i=e[i].next){
		search(e[i].v);
	}
	
	LL jd=root[x];
	while (s[x]>m){
		ss[x]--;
		s[x]-=h[jd];
		jd=merge(ls[jd],rs[jd]);
	}
	root[x]=jd;
	
	root[a[x]]=merge(root[a[x]],jd);
	s[a[x]]+=s[x]; ss[a[x]]+=ss[x];
	if (ss[x]*l[x]>ans) ans=ss[x]*l[x];
}
int main(){
	scanf("%lld%lld",&n,&m);
	for (int i=1;i<=n;i++){
		scanf("%lld%lld%lld",&a[i],&c[i],&l[i]);
		add(a[i],i);
	}
	
	for (int i=0;i<=n;i++){
		h[i]=c[i];
		ss[i]++; s[i]+=c[i];
		root[i]=i;
	}
	
	search(0);
		
	printf("%lld\n",ans);
	
	return 0;
}