问题即求每个节点的子树内，按权值从小到大排序，前 \(k\) 个 \(c_i\) 加起来不超过 \(m\)，求 \(\max \{k * l_u \}\)
可以想到左偏树能快速维护子树内所有权值的大小关系
每个节点维护一个大根堆，然后合并和子树的堆
先把所有值都给加上，当它们大于 \(m\)，就一个一个pop，直到小于等于 \(m\)
然后就
做完了
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
inline ll read() {
ll x = 0, f = 1; char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
return x * f;
}
const int N = 1e5 + 10;
struct E { int v, ne; } e[N];
int ls[N], rs[N], n, M, dis[N], head[N], cnt;
ll m, C[N], L[N], sum[N], sz[N], ans;
void add(int u, int v) {
e[++cnt] = (E){v, head[u]};
head[u] = cnt;
}
int merge(int u, int v) {
if (!u || !v) return u + v;
if (C[u] < C[v]) swap(u, v);
rs[u] = merge(rs[u], v);
if (dis[ls[u]] < dis[rs[u]]) swap(ls[u], rs[u]);
dis[u] = dis[rs[u]] + 1;
return u;
}
int pop(int u) { return merge(ls[u], rs[u]); }
int dfs(int u) {
int A = u, B;
sum[u] = C[u]; sz[u] = 1;
for (int i = head[u]; i; i = e[i].ne) {
int v = e[i].v;
B = dfs(v);
A = merge(A, B);
sum[u] += sum[v]; sz[u] += sz[v];
}
while (sum[u] > m) {
sum[u] -= C[A]; sz[u]--;
A = pop(A);
}
ans = max(ans, L[u] * sz[u]);
return A;
}
int main() {
n = read(), m = read();
for (int i = 1; i <= n; i++) {
int u = read();
if (!u) M = i;
else add(u, i);
C[i] = read();
L[i] = read();
}
dfs(M);
printf("%lld\n", ans);
return 0;
}