Solution
想存一下左偏树的模板。
我们发现容量上限是不变的,那么就可以贪心地依次选取每个点子树中的最大值删去。
就可以啦。
Code
#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
int head[N], dot[N << 1], nxt[N << 1], cnt, m;
ll ans;
struct LT {
int f[N], son[N][2], val[N], dis[N], siz[N];
ll s[N], l[N];
void init(const int n) {
for(int i = 1; i <= n; ++ i) {
son[i][0] = son[i][1] = dis[i] = s[i] = 0;
f[i] = i; siz[i] = 1;
}
}
int Find(const int x) {return x == f[x] ? x : f[x] = Find(f[x]);}
bool cmp(const int x, const int y) {return Find(x) == Find(y);}
int unite(int x, int y) {
if(! x || ! y) return x + y;
if(val[x] < val[y]) swap(x, y);
son[x][1] = unite(son[x][1], y); f[son[x][1]] = x;
if(dis[son[x][0]] < dis[son[x][1]]) swap(son[x][0], son[x][1]);
dis[x] = dis[son[x][1]] + 1;
return x;
}
int del(const int x) {
int l = son[x][0], r = son[x][1];
son[x][0] = son[x][1] = dis[x] = 0;
f[l] = l; f[r] = r;
return unite(l, r);
}
void solve(const int x, const int fa) {
for(int i = head[x]; i; i = nxt[i]) {
int v = dot[i];
if(v == fa) continue;
solve(v, x);
siz[x] += siz[v]; s[x] += s[v];
f[x] = unite(f[x], f[v]);
}
while(s[x] > m) {
s[x] -= val[f[x]]; -- siz[x];
f[x] = unite(son[f[x]][0], son[f[x]][1]);
}
ans = max(ans, l[x] * siz[x]);
}
}T;
void addEdge(const int u, const int v) {
dot[++ cnt] = v; nxt[cnt] = head[u]; head[u] = cnt;
}
int read() {
int x = 0, f = 1; char s;
while((s = getchar()) < ‘0‘ || s > ‘9‘) if(s == ‘-‘) f = -1;
while(s >= ‘0‘ && s <= ‘9‘) {x = (x << 1) + (x << 3) + (s ^ 48); s = getchar();}
return x * f;
}
int main() {
int x, n, root;
n = read(), m = read();
T.init(n);
for(int i = 1; i <= n; ++ i) {
x = read(), T.s[i] = T.val[i] = read(), T.l[i] = read();
if(x) addEdge(x, i);
else root = i;
}
T.solve(root, 0);
printf("%lld\n", ans);
return 0;
}