「bsoj1702」搞 - 可并堆

题目大意

你可以在一棵树中选出一个管理者$x$，然后在他的子树中选$k$个人（管理者不一定要选），钱数加起来不超过$M$，使得$k*b_x$最大。

---

题目分析

这不是「APIO2012」派遣原题吗~

发现题目中的式子只与人数有关，并未与特定的人有关。
那么我们可以得出一个贪心思路：
从下往上递归这棵树，将所有儿子选的人合并起来，若钱数大于$M$，不断弹出最大耗钱的人，然后统计答案。

一般的数据结构难以实现合并，可以采用可并堆。

---

代码

#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 int Get_Int() {
	int 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;
struct LeftSideTree { //左偏树（大根堆） 
	int n,lson[maxn],rson[maxn],dist[maxn];
	LL a[maxn];
	inline void init(int n,LL a[]) {
		this->n=n;
		for(int i=1; i<=n; i++)this->a[i]=a[i];
	}
	inline int merge(int x,int y) { //均为下标 
		if(x==0||y==0)return x+y;
		if(a[x]<a[y])swap(x,y); //小根堆改成>
		rson[x]=merge(rson[x],y);
		if(dist[rson[x]]>dist[lson[x]])swap(lson[x],rson[x]); //维护左偏平衡时间 
		if(!rson[x])dist[x]=0;
		else dist[x]=dist[rson[x]]+1;
		return x;
	}
	inline int del(int x) { //删除结点返回左右儿子新堆下标 
		int tmp=merge(lson[x],rson[x]);
		lson[x]=rson[x]=0;
		return tmp;
	}
} heap;
int n,root[maxn];
LL m,sum[maxn],Cost[maxn],Size[maxn],b[maxn],ans=0;
vector<int>edges[maxn];
void AddEdge(int x,int y) {
	edges[x].push_back(y);
}
void Dfs(int Now) {
	sum[Now]=Cost[Now];
	Size[Now]=1;
	root[Now]=Now;
	for(auto& Next:edges[Now]) {
		Dfs(Next);
		Size[Now]+=Size[Next];
		sum[Now]+=sum[Next];
		root[Now]=heap.merge(root[Now],root[Next]);
	}
	while(sum[Now]>m) {
		sum[Now]-=Cost[root[Now]];
		Size[Now]--;
		root[Now]=heap.del(root[Now]);
	}
	ans=max(ans,b[Now]*Size[Now]);
}
int main() {
	n=Get_Int();
	m=Get_Int();
	for(int i=1; i<=n; i++) {
		int f=Get_Int();
		Cost[i]=Get_Int();
		b[i]=Get_Int();
		if(f)AddEdge(f,i);
	}
	heap.init(n,Cost);
	Dfs(1);
	printf("%lld\n",ans);
	return 0;
}