[文章目录]
Description
在这个帮派里，有一名忍者被称之为 Master。除了 Master以外，每名忍者都有且仅有一个上级。所有与他们工作相关的指令总是由上级发送给他的直接下属，而不允许通过其他的方式发送。现在你要招募一批忍者，并把它们派遣给顾客。你需要为每个被派遣的忍者 支付一定的薪水，总额不超过你的预算。另外，为了发送指令，你需要选择一名忍者作为管理者，要求这个管理者可以向所有被派遣的忍者 发送指令，在发送指令时，任何忍者（不管是否被派遣）都可以作为消息的传递人。管理者自己可以被派遣，也可以不被派遣。当然，如果管理者没有被排遣，就不需要支付管理者的薪水。你的目标是在预算内使顾客的满意度最大。这里定义顾客的满意度为派遣的忍者总数乘以管理者的领导力水平，其中每个忍者的领导力水平也是一定的。写一个程序，给定每一个忍者 i的上级 Bi，薪水Ci，领导力L i，以及支付给忍者们的薪水总预算 M，输出在预算内满足上述要求时顾客满意度的最大值。1 ≤N ≤ 100,000 忍者的个数；1 ≤M ≤ 1,000,000,000 薪水总预算； 0 ≤Bi < i 忍者的上级的编号；1 ≤Ci ≤ M 忍者的薪水；1≤Li ≤1,000,000,000 忍者的领导力水平。
可并堆
就是求一颗子树，使得根节点的领导能力乘以子树中所选薪水和不超过m的最多选择个数最大。
所选的一定是子树忍者薪水最小的几个。维护一个薪水堆，当堆中的总和大于m的时候删除薪水最多的那个忍者。然后在dfs的时候合并堆。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
int n;
ll m,c[101000],w[101000],ans;
int head[101000],to[101000],nxt[101000],cnt;
void add(int x,int y)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt;
}
int rt[101000],siz[101000];
ll sum[101000];
struct heap
{
int ls,rs,nvl;
}he[101000];
int merge(int x,int y)
{
if(!x||!y) return x|y;
if(w[x]<w[y]) swap(x,y);
he[x].rs=merge(he[x].rs,y);
if(he[he[x].ls].nvl<he[he[x].rs].nvl) swap(he[x].ls,he[x].rs);
he[x].nvl=he[he[x].rs].nvl+1;
return x;
}
void pop(int &x)
{
int t=merge(he[x].ls,he[x].rs);
sum[t]=sum[x]-w[x]; siz[t]=siz[x]-1; x=t;
}
void dfs(int x)
{
he[x].nvl=1; rt[x]=x; sum[x]=w[x]; siz[x]=1;
for(int i=head[x];i;i=nxt[i])
{
dfs(to[i]);
int t=merge(rt[x],rt[to[i]]);
sum[t]=sum[rt[x]]+sum[rt[to[i]]];
siz[t]=siz[rt[x]]+siz[rt[to[i]]];
rt[x]=t;
while(sum[rt[x]]>m) pop(rt[x]);
}
ans=max(ans,(ll)siz[rt[x]]*c[x]);
}
int main()
{
scanf("%d%lld",&n,&m); int x,y;
for(int i=1;i<=n;++i)
{
scanf("%d%lld%lld",&x,&w[i],&c[i]);
if(x==0) y=i;
else add(x,i);
}
dfs(y); printf("%lld\n",ans);
return 0;
}