BZOJ 2809 [APIO2012] 派遣 Dispatching

题目大意

给你一棵以1为根的树，对于每个节点的子树，找出尽量多的点，使得这些点的点权之和不超过m，并把选出节点的个数与该节点的另一种权值的乘积更新到ans中，求ans的最大值。

这题一看就是在树上维护集合……想到的第一个东西就是权值线段树……当然这么写似乎可过？

实际上这题是可并堆……维护树上集合的另一种方式。

DFS到一个点，先DFS他的儿子之后上传。此时贪心的删除花销大的点直到总花销不超过m，之后直接统计即可。

#include <cstdio>
#include <algorithm>
using namespace std;

#define N 100010

int n,rt[N],fa[N];
long long m,c[N],l[N],ans;

int to[N],nex[N],head[N],tot;

inline void AE(int tx,int ty){to[++tot]=ty,nex[tot]=head[tx],head[tx]=tot;}

int h[N],ls[N],rs[N];
long long sum[N],cnt[N];

int merge(int tx,int ty)
{
	if(!tx) return ty;
	if(!ty) return tx;
	if(c[tx]<c[ty]) swap(tx,ty);
	rs[tx]=merge(rs[tx],ty);
	if(h[ls[tx]]<h[rs[tx]]) swap(ls[tx],rs[tx]);
	h[tx]=rs[tx]?h[rs[tx]]+1:0;
	return tx;
}

void DFS(int pos)
{
	for(int i=head[pos];i;i=nex[i])
	{
		DFS(to[i]);
		sum[pos]+=sum[to[i]];
		cnt[pos]+=cnt[to[i]];
		rt[pos]=merge(rt[to[i]],rt[pos]);
	}
	while(sum[pos]>m&&cnt[pos])
		sum[pos]-=c[rt[pos]],cnt[pos]--,rt[pos]=merge(ls[rt[pos]],rs[rt[pos]]);
	ans=max(ans,cnt[pos]*l[pos]);
}

int main()
{
	scanf("%d%lld",&n,&m);
	for(int i=1;i<=n;++i) scanf("%d%lld%lld",fa+i,c+i,l+i),AE(fa[i],i);
	for(int i=1;i<=n;++i) rt[i]=i,sum[i]=c[i],cnt[i]=1;
	DFS(1);
	printf("%lld\n",ans);
	return 0;
}