题目描述
在这个帮派里，有一名忍者被称之为Master。除了Master以外，每名忍者都有且仅有一个上级。为保密，同时增强忍者们的领导力，所有与他们工作相关的指令总是由上级发送给他的直接下属，而不允许通过其他的方式发送。
现在你要招募一批忍者，并把它们派遣给顾客。你需要为每个被派遣的忍者支付一定的薪水，同时使得支付的薪水总额不超过你的预算。另外，为了发送指令，你需要选择一名忍者作为管理者，要求这个管理者可以向所有被派遣的忍者发送指令，在发送指令时，任何忍者（不管是否被派遣）都可以作为消息的传递人。管理者自己可以被派遣，也可以不被派遣。当然，如果管理者没有被排遣，你就不需要支付管理者的薪水。
你的目标是在预算内使顾客的满意度最大。这里定义顾客的满意度为派遣的忍者总数乘以管理者的领导力水平，其中每个忍者的领导力水平也是一定的。
写一个程序，给定每一个忍者i的上级Bi，薪水Ci，领导力Li，以及支付给忍者们的薪水总预算M，输出在预算内满足上述要求时顾客满意度的最大值。
1 ≤ N ≤ 100,000 忍者的个数；
1 ≤ M ≤ 1,000,000,000 薪水总预算；
0 ≤ Bi < i 忍者的上级的编号；
1 ≤ Ci ≤ M 忍者的薪水；
1 ≤ Li ≤ 1,000,000,000 忍者的领导力水平。
题解
可以想到贪心的思路，对于每个节点，找他及其子树薪水最小的一些，加起来不超过m；
这时就可以运用到可并堆了，左偏树是其中一种实现方式。
#include<bits/stdc++.h> using namespace std; //左偏树 #define ll long long const int maxn=100005; int n; ll m,ans; int root[maxn],ls[maxn],rs[maxn],dis[maxn];//root:i及其子树形成的大根堆的根 dis:i到外节点的距离 ll sum[maxn],size[maxn];//i及其子树形成的根的薪水和、人数 struct person{ int fa; ll cost,power;//上级，薪水，领导力 }a[maxn]; template<class T>inline void read(T &x){ x=0;char ch=getchar(); while(!isdigit(ch)) ch=getchar(); while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} } void build(int x){ root[x]=x; sum[x]=a[x].cost; size[x]=1; } int merge(int A,int B){ if(!A) return B; if(!B) return A; if(a[A].cost<a[B].cost) swap(A,B); rs[A]=merge(rs[A],B); if(dis[rs[A]]>dis[ls[A]]) swap(ls[A],rs[A]); if(!rs[A]) dis[A]=0; else dis[A]=dis[rs[A]]+1; return A; } int main(){ read(n);read(m); for(int i=1;i<=n;i++){ int x;ll y,z; read(x);read(y);read(z); a[i]=(person){x,y,z}; build(i);//自身成为一个堆 ans=max(ans,z); } for(int i=n;i;i--){//并且每一个忍者的老板的编号一定小于自己的编号Bi<i，所以可以倒着枚举，dfs栈可能爆栈 int f=a[i].fa; root[f]=merge(root[i],root[f]); size[f]+=size[i]; sum[f]+=sum[i]; while(sum[f]>m){ sum[f]-=a[root[f]].cost; root[f]=merge(ls[root[f]],rs[root[f]]); size[f]--; } ans=max(ans,a[f].power*size[f]); } printf("%lld",ans); }
还可以用可合并值域线段树，现在还不会，之后再写。