显然这种上下级的关系构成一个树形结构。
我们可以枚举一个管理者，然后再来看看他的满意度水平到底有多高。
因为要求这个管理者可以向所有人发送指令，所以他只能选他的子树中的点。
把他所有选的人放在同一个集合内，要求总薪水小于M且人数最多（因为满意度只和人数和管理者的领导力有关）。
那我们就得到一个思路：把所有子树内的人放到一个集合里，然后如果总薪水大于M，就把薪水最大的人干掉，直到薪水小于M。
如果这个集合是个堆就可以在$O(1)$的复杂度内找到薪水最大的人，并在$O(log{n})$的复杂度内干掉他。
可是这样做总复杂度是$O(n^2)$还是太慢。
考虑优化。
我们发现每个人最终的集合和它的孩子的集合是有大部分重复的，用线段树合并的思想，我们可以把他的儿子的集合并到他的上面。
这就要用到可并堆了（这里用左偏树）。
然后就可以在$O(n\log{n})$的复杂度内解决问题了。
具体实现的时候维护一个size和一个sum分别代表一个人的集合的大小和总薪水。
再维护一个root代表堆顶。
这是树上左偏树的基本套路。
#include <iostream> #include <cstdio> using namespace std; typedef long long ll; const ll N = 100010; struct Leftist_Tree{ ll dist, val, ls, rs; }tr[N]; struct node{ ll pre, to; }edge[N << 1]; ll head[N], tot; ll n, m; ll c[N], w[N], ans; ll rt[N], sum[N], sz[N]; void add(ll u, ll v) { edge[++tot] = node{head[u], v}; head[u] = tot; } ll Merge(ll u, ll v) { if (!u || !v) return u | v; if (tr[u].val < tr[v].val) swap(u, v); tr[u].rs = Merge(tr[u].rs, v); if (tr[tr[u].ls].dist < tr[tr[u].rs].dist) swap(tr[u].ls, tr[u].rs); tr[u].dist = tr[tr[u].rs].dist + 1; return u; } void dfs(ll x, ll fa) { for (ll i = head[x]; i; i = edge[i].pre) { ll y = edge[i].to; if (y == fa) continue; dfs(y, x); rt[x] = Merge(rt[x], rt[y]); sum[x] += sum[y]; sz[x] += sz[y]; } while (sum[x] > m && sz[x]) { sum[x] -= tr[rt[x]].val; rt[x] = Merge(tr[rt[x]].ls, tr[rt[x]].rs); sz[x]--; } ans = max(ans, sz[x] * w[x]); } int main() { cin >> n >> m; for (ll i = 1; i <= n; i++) { ll b; cin >> b >> c[i] >> w[i]; if (b != 0) { add(b, i); add(i, b); } rt[i] = i; tr[i].ls = tr[i].rs = tr[i].dist = 0; tr[i].val = sum[i] = c[i]; sz[i] = 1; } dfs(1, 0); cout << ans; return 0; }