[APIO2012]派遣

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。

输出格式：

输出一个数，表示在预算内顾客的满意度的最大值。

输入样例：

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 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
#include
using namespace std;
const int N=100005;
inline int read()
{
    RG int x=0,w=1;RG char ch=getchar();
    while(ch‘9‘){if(ch==‘-‘)w=-1;ch=getchar();}
    while(ch>=‘0‘&&chdist[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