```cpp
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
struct Node {
int s[2], c, sz, dis;
long long sum;
Node() {};
Node(int _c) { s[0] = s[1] = 0; dis = sz = 1; sum = c = _c; }
} tr[maxn];
int n, f[maxn], b[maxn], L[maxn];
long long m, ans;
void init() {
for (int i = 1; i <= n; i++) f[i] = i;
}
void push_up(int x) {
int l = tr[x].s[0], r = tr[x].s[1];
tr[x].dis = tr[r].dis + 1;
tr[x].sz = tr[l].sz + tr[r].sz + 1;
tr[x].sum = tr[l].sum + tr[r].sum + tr[x].c;
}
int merge(int x, int y) {
if (!x || !y) return x + y;
if (tr[x].c < tr[y].c) swap(x, y);
int &l = tr[x].s[0], &r = tr[x].s[1];
r = merge(r, y);
if (tr[l].dis < tr[r].dis) swap(l, r);
push_up(x);
return x;
}
void pop(int x) {
int l = tr[f[x]].s[0], r = tr[f[x]].s[1];
f[x] = merge(l, r);
}
int main() {
scanf("%d%lld", &n, &m);
init();
for (int i = 1; i <= n; i++) {
int c;
scanf("%d%d%d", b+i, &c, L+i);
tr[i] = Node(c);
}
for (int i = n; i >= 1; i--) {
while (tr[f[i]].sum > m) pop(i);
long long tmp = (long long) tr[f[i]].sz * L[i];
ans = max(ans, tmp);
if (b[i]) f[b[i]] = merge(f[b[i]], f[i]);
}
printf("%lld\n", ans);
return 0;
}
```
我换了一种写法。
$f_i$ 表示 $i$ 子树所代表的左偏树的根节点编号。
这样合并的话只要使用赋值就行了,因为路径压缩 $fa$ 可能会有问题(?)也不好调。
你可以先参考我的实现方式,有不懂的问题再来找我。
by Rosaya @ 2023-04-06 17:06:13
@[Rosaya](/user/191748) 谢谢大佬,根据大佬的提示,我发现是我主函数里面没有调用路径压缩,我把主函数里面:
```c++
if (b[i]) f[b[i]] = merge(f[b[i]], f[i]);
```
改成:
```c++
if (b[i] && find(b[i]) != x) merge(find(b[i]), x);
```
就过了。谢谢大佬,红包我私信您哈
by quanjun @ 2023-04-06 18:09:09