云剪贴板 grrjs6ii

# 不是板子

简化题意：

$n$个点组成一棵树，每个点都有一个领导力和费用，可以让一个点当领导**即**所有节点的父亲，然后在这个点的子树中选择一些费用之和不超过$m$的点，得到领导的领导力乘选择的点的个数（领导可不被选择）的利润。求利润最大值。 $n≤100000$ 。

思路：

从叶子节点开始，每个点开始是一个大根堆，堆里的就是这个点的人。

往父亲那里合并堆，记录堆的大小，费用的总和。

从儿子合并完毕后，在每个节点，不断踢出费用最大的人，即删除堆顶，直到费用的总和$<=m$这就是这个点的最优方案了。（显然，花费最小的都留下了）

对于每个点，用这个点的领导力乘堆的大小尝试更新答案即可。

代码:

```cpp
#include<bits/stdc++.h>
#define val(i) tr[i].val
#define fa(i) tr[i].fa
#define lis(i) tr[i].lis
#define l(i) tr[i].lt
#define r(i) tr[i].rt
#define dist(i) tr[i].dist
#define int long long
const int Maxn = 1e5+100;
using namespace std;
int n,m,root[Maxn],sum[Maxn],ans,siz[Maxn];
struct node{
	int dist,val,fa,lis,lt,rt;
}tr[Maxn];
int merge(int x,int y) {
	if(!x||!y) return x|y;
	if(val(x)<val(y)) swap(x,y);
	r(x)=merge(r(x),y);
	if(dist(l(x))<dist(r(x))) swap(l(x),r(x));
	dist(x)=dist(r(x))+1;
	return x;
}
int pop(int x) {
	return merge(l(x),r(x));
}
signed main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;++i) scanf("%lld%lld%lld",&fa(i),&val(i),&lis(i));
	for(int i=1;i<=n;++i) root[i]=i,sum[i]=val(i),siz[i]=1;
	for(int i=n;i>=1;--i) {
		while(sum[i]>m) {
			sum[i]-=val(root[i]);--siz[i];
			root[i]=pop(root[i]);
			if(!siz[i]) {
				root[i]=-1; break;
			}
		}
		if(root[i]!=-1) {
			ans=max(ans,lis(i)*siz[i]);
			sum[fa(i)]+=sum[i];siz[fa(i)]+=siz[i];
			root[fa(i)]=merge(root[fa(i)],root[i]);
		}
	}
	printf("%lld",ans);
	return 0;
}
```