P1552 [APIO2012]调派https://www.luogu.org/problemnew/show/P1552
标题问题配景
在一个忍者的帮派里，一些忍者们当选中调派给顾客，然后依据本身的事情获取报偿。
标题问题描述
在这个帮派里，有一名忍者被称之为\(Master\)。除了\(Master\)以外，每名忍者都有且仅有一个上级。为保密，同时增强忍者们的带领力，所有与他们事情相关的指令总是由上级发送给他的直接部属，而不允许通过其他的方法发送。
此刻你要招募一批忍者，并把它们调派给顾客。你需要为每个被调派的忍者付出必然的薪水，同时使得付出的薪水总额不赶过你的预算。此外，为了发送指令，你需要选择一名忍者作为打点者，要求这个打点者可以向所有被调派的忍者发送指令，在发送指令时，任何忍者（不管是否被调派）都可以作为动静的通报人。打点者本身可以被调派，也可以不被调派。固然，如果打点者没有被排遣，你就不需要付出打点者的薪水。
你的方针是在预算内使顾客的对劲度最大。这里界说顾客的对劲度为调派的忍者总数乘以打点者的带领力程度，此中每个忍者的带领力程度也是必然的。
写一个措施，给定每一个忍者\(i\)的上级\(B_i\)，薪水\(C_i\)，带领力\(L_i\)，以及付出给忍者们的薪水总预算\(M\)，输出在预算内满足上述要求时顾客对劲度的最大值。
输入格局：
第一行包罗两个整数\(N\)和\(M\)，，此中N暗示忍者的个数，\(M\)暗示薪水的总预算。
接下来\(N\)行描述忍者们的上级、薪水以及带领力。此中的第\(i\)行包罗三个整数\(B_i\),\(C_i\),\(L_i\)分袂暗示第\(i\)个忍者的上级，薪水以及带领力。\(Master\)满足\(B_i=0\)，并且每一个忍者的老板的编号必然小于本身的编号\(B_i<i\)。
输格外式：
输出一个数，暗示在预算内顾客的对劲度的最大值。
输入样例：
5 4
0 3 3
1 3 5
2 2 2
1 2 4
2 3 1
输出样例：
6
说明
1 ≤ N ≤ 100,000 忍者的个数；
1 ≤ M ≤ 1,000,000,000 薪水总预算；
0 ≤ Bi < i 忍者的上级的编号；
1 ≤ Ci ≤ M 忍者的薪水；
1 ≤ Li ≤ 1,000,000,000 忍者的带领力程度。
对付 30%的数据，N ≤ 3000。
枚举每个点作为打点者,则标题问题所求为该点子树中一个权值和小于\(M\)的点集,并使该点集中点的数目最大化.
设该点集点数为\(num_i\),则有最终答案\(Ans=max(Ans,l_i*num_i)\).
考虑对每个节点建堆,对付每个非叶节点,将该节点与每个儿子节点合并(左偏树),维护堆中节点数和堆中节点的点权和.
细节:sum[]和Ans需要开long long
#define LL long long
#define RG register
#include<cstdio>
#include<iostream>
using namespace std;
const int N=100005;
inline int read()
{
RG int x=0,w=1;RG char ch=getchar();
while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)w=-1;ch=getchar();}
while(ch>=‘0‘&&ch<=‘9‘)x=x*10+ch-‘0‘,ch=getchar();
return x*w;
}
int n,m,cnt;
LL Ans;
int b[N],c[N],l[N],last[N],num[N],root[N],ls[N],rs[N],dist[N];
LL sum[N];
struct edge{
int to,next;
}e[N];
inline void insert(int u,int v)
{
e[++cnt]=(edge){v,last[u]};last[u]=cnt;
}
int find(int x){return x==root[x]?x:root[x]=find(root[x]);}//并查集搜根,路径压缩
int Merge(int a,int b)
{
if(!a||!b)return a+b;
if(c[a]<c[b])swap(a,b);
rs[a]=Merge(rs[a],b);
if(dist[rs[a]]>dist[ls[a]])swap(rs[a],ls[a]);
dist[a]=dist[rs[a]]+1;
return a;
}
void dfs(int now)//从根节点向下dfs,回溯时合并
{
num[now]=1;//建堆
sum[now]=c[now];
for(RG int i=last[now];i;i=e[i].next)
{
int v=e[i].to;
dfs(v);
int fv=find(v),fn=find(now);//找到节点地址堆的根[now和v不必然是地址堆的根]
root[now]=Merge(fn,fv);//合并上下级
sum[now]+=sum[v];
num[now]+=num[v];
while(sum[now]>m)//点权和大于M则需要pop
{
num[now]--;
sum[now]-=c[root[now]];
int ll=ls[root[now]],rr=rs[root[now]];
root[now]=Merge(ll,rr);//删除堆顶
root[ll]=ll==root[now]?ll:root[ll];//防备搜根时呈现死循环,将新根地址左偏树的根置为本身
root[rr]=rr==root[now]?rr:root[rr];
}
}
Ans=max(Ans,1ll*l[now]*num[now]);
}
int main()
{
n=read();
m=read();
for(RG int i=1;i<=n;i++)
{
root[i]=i;
b[i]=read();
c[i]=read();
l[i]=read();
if(b[i])insert(b[i],i);
}
dfs(1);
printf("%lld\n",Ans);
return 0;
}
