dispatching
在一个忍者的帮派里，一些忍者们被选中派遣给顾客，然后依据自己的工作获取报偿。在这个帮派里，有一名忍者被称之为 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 忍者的领导力水平。
分析
假设确定了(i)号节点，那么就应该是在(i)号点的子树中从小到大选择，直到代价和大于(M)。可以使用堆来帮助选择，复杂度(O(N^2cdot log N))。
从下到上考虑，在(i)号节点所选的点一定是在它的儿子节点中选的点或者(i)号节点，所以只需要将它的儿子中选的点拿出来建堆。同样可以考虑启发式合并，复杂度为(O(N cdot log^2N))
其实这个是涉及到两个堆合并的问题，那么就可以使用可并堆了，而左偏树是一种高效可并堆，所以使用左偏树。
转化一下，对于每个节点维护子树大根堆，若堆中忍者薪水和大于(M)，则pop。时间复杂度(O(N cdot log N))
UPD：其实不用写左偏树，直接用pd_ds的堆就好了。
__gnu_pbds::priority_queue
#include<ext/pb_ds/priority_queue.hpp>
#define pbds __gnu_pbds
pbds::priority_queue<int,std::less<int>,pbds::pairing_heap_tag> pq;
point_iterator push(const_reference);
void modify(point_iterator, const_reference);
void erase(point_iterator);
void join(priority_queue &other); // other->this，other被清空
typedef long long ll;
const int INF=0x7fffffff;
const int MAXN=1e5+7;
struct Edge
{
int nx,to;
}E[MAXN];
int head[MAXN],ecnt;
void addedge(int x,int y)
{
E[++ecnt].to=y;
E[ecnt].nx=head[x],head[x]=ecnt;
}
int n,m;
int c[MAXN],l[MAXN];
int root[MAXN],rcnt,size[MAXN];
ll sum[MAXN],ans;
struct LeftTree
{
int ch[MAXN][2];
int val[MAXN],dis[MAXN];
int merge(int x,int y)
{
if(x==0||y==0)
return x+y;
if(val[x]<val[y])
swap(x,y);
ch[x][1]=merge(ch[x][1],y);
if(dis[ch[x][0]]<dis[ch[x][1]])
swap(ch[x][0],ch[x][1]);
dis[x]=dis[ch[x][1]]+1;
return x;
}
int&top(int x)
{
return val[x];
}
void pop(int&x)
{
x=merge(ch[x][0],ch[x][1]);
}
}LT;
void dfs(int x)
{
root[x]=++rcnt;
LT.val[rcnt]=c[x];
size[x]=1;
sum[x]=c[x];
for(int i=head[x];i;i=E[i].nx)
{
int y=E[i].to;
dfs(y);
size[x]+=size[y];
sum[x]+=sum[y];
root[x]=LT.merge(root[x],root[y]);
}
while(sum[x]>m)
{
sum[x]-=LT.top(root[x]);
LT.pop(root[x]);
--size[x];
}
ans=max(ans,(ll)size[x]*l[x]);
}
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
read(n);read(m);
for(int i=1;i<=n;++i)
{
int fa;
read(fa);
addedge(fa,i);
read(c[i]);read(l[i]);
}
dfs(0);
printf("%lld
",ans);
// fclose(stdin);
// fclose(stdout);
return 0;
}