现在你要招募一批忍者，并把它们派遣给顾客。你需要为每个被派遣的忍者支付一定的薪水，同时使得支付的薪水总额不超过你的预算。另外，为了发送指令，你需要选择一名忍者作为管理者，要求这个管理者可以向所有被派遣的忍者发送指令，在发送指令时，任何忍者（不管是否被派遣）都可以作为消息的传递人。管理者自己可以被派遣，也可以不被派遣。当然，如果管理者没有被排遣，你就不需要支付管理者的薪水。
你的目标是在预算内使顾客的满意度最大。这里定义顾客的满意度为派遣的忍者总数乘以管理者的领导力水平，其中每个忍者的领导力水平也是一定的。
写一个程序，给定每一个忍者 i 的上级 Bi ，薪水 Ci ，领导力 Li ，以及支付给忍者们的薪水总预算 M ，输出在预算内满足上述要求时顾客满意度的最大值。
分析
首先根据上级与下级之间的关系，我们可以建出一棵树，然后我们想要知道以每个忍者作为管理者顾客满意度的最大值。显然以 u 作为管理者，能够派遣的忍者一定在它的子树中，我们可以 dfs 递归求出，维护一个左偏树，利用它大根堆和可合并的性质，首先将它的子节点的堆合并，同时统计总共的薪水和人数，然后如果薪水超过预算，我们每次去掉堆顶，也就是去掉最贵的忍者，然后求出满意度取 max 。
代码
//=========================
// author:hliwen
// date:2020.1.18
//=========================
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 100005
#define il inline
#define re register
#define DEBUG puts("ok")
#define tie0 cin.tie(0),cout.tie(0)
#define fastio ios::sync_with_stdio(false)
#define File(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout)
using namespace std;
typedef long long ll;
template <typename T> inline void read(T &x) {
T f = 1; x = 0; char c;
for (c = getchar(); !isdigit(c); c = getchar()) if (c == '-') f = -1;
for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
x *= f;
}
ll ans;
int n, m, Master;
ll sum[N], val[N], l[N];
int tot[N], rs[N], ls[N], dis[N];
int to[N], nxt[N], head[N], cnt;
void insert(int u, int v) {
to[++cnt] = v, nxt[cnt] = head[u], head[u] = cnt;
}
int merge(int x, int y) {
if (!x || !y) return x + y;
if (val[x] < val[y]) swap(x, y);
rs[x] = merge(rs[x], y);
if (dis[ls[x]] < dis[rs[x]]) swap(ls[x], rs[x]);
dis[x] = dis[rs[x]] + 1;
return x;
}
int pop(int x) {
return merge(ls[x], rs[x]);
}
int dfs(int u) {
int x = u, v;
sum[u] = val[u], tot[u] = 1;
for (int i = head[u]; i; i = nxt[i]) {
v = to[i];
int y = dfs(v);
x = merge(x, y);
sum[u] += sum[v], tot[u] += tot[v];
}
while (sum[u] > m) {
sum[u] -= val[x], tot[u] --;
x = pop(x);
}
ans = max(ans, tot[u] * l[u]);
return x;
}
int main() {
int x;
read(n), read(m);
for (int i = 1; i <= n; ++i) {
read(x), read(val[i]), read(l[i]);
if (!x) Master = i;
else insert(x, i);
}
dfs(Master);
printf("%lld", ans);
return 0;
}