题目：派遣
思路：
左偏树。
add[i]表示以i为根，子树中所需的工资之和。
sum[i]表示以i为根，子树中被派遣的节点个数。
先从根节点开始dfs遍历整棵树，在回朔后更新add和sum。
由于这题只关心选择的节点个数，所以可以用贪心的思想，即在master一定时，选择所需工资尽量少的节点一定是最优的。
所以可以用左偏树，对于节点u，每次回朔时就要把i的所有子树所在的大根堆合并，add[i]加上add[child]，sum[i]++。
如果在某个时刻add[i]>m，此时就要删除以i所在左偏树中的最大值。
最后的答案ans=max{add[i]*w[i]}，w[i]为领导力。
注意：在删除某个节点后，这个节点的父指针 fa 要指向自己的孩子。因为它的上层仍然要利用它来找到它的子树所在的堆。
代码：
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <cstring>
#include <map>
using namespace std;#define maxn 100000
#define ll long longint n,m;vector<int> a[maxn+5];
int v[maxn+5],w[maxn+5];int fa[maxn+5],lch[maxn+5],rch[maxn+5];
int d[maxn+5];ll sum[maxn+5],add[maxn+5];void init() {for(int i=0; i<=maxn; i++) {a[i].clear();fa[i]=i;}memset(lch,0,sizeof(lch));memset(rch,0,sizeof(rch));memset(sum,0,sizeof(sum));memset(add,0,sizeof(add));
}int merge(int x,int y) {if(x==0) return y;if(y==0) return x;if(v[x]<v[y]) swap(x,y);rch[x]=merge(rch[x],y);if(d[lch[x]]<d[rch[x]]) swap(lch[x],rch[x]);d[x]=d[rch[x]]+1;fa[lch[x]]=x,fa[rch[x]]=x;return x;
}int find(int x) {while(fa[x]!=x) {x=fa[x];}return x;
}void Pop(int x){int rt=find(x);add[x]-=v[rt];sum[x]--;fa[lch[rt]]=lch[rt],fa[rch[rt]]=rch[rt];merge(lch[rt],rch[rt]);if(lch[rt]) fa[rt]=find(lch[rt]);else if(rch[rt]) fa[rt]=find(rch[rt]);else fa[rt]=rt;lch[rt]=rch[rt]=0,v[rt]=0;
}ll dfs(int x) {ll ans=0;add[x]+=v[x];sum[x]++;while(add[x]>m) Pop(x);for(int i=0; i<a[x].size(); i++) {int y=a[x][i];ans=max(ans,dfs(y));add[x]+=add[y];sum[x]+=sum[y];merge(find(x),find(y));while(add[x]>m) Pop(x);}return max(ans,sum[x]*w[x]);
}int main() {scanf("%d%d",&n,&m);init();int rt;for(int i=1; i<=n; i++) {int x,y,z;scanf("%d%d%d",&x,&v[i],&w[i]);a[x].push_back(i);if(x==0) rt=i;}printf("%lld",dfs(rt));return 0;
}