bzoj 2809 左偏树\平衡树启发式合并

/**************************************************************
    Problem: 2809
    User: BLADEVIL
    Language: C++
    Result: Accepted
    Time:3604 ms
    Memory:8060 kb
****************************************************************/
 
//By BLADEVIL
#include <cstdio>
#include <algorithm>
#define maxn 100010
#define LL long long
 
using namespace std;
 
int n,m,l;
int left[maxn],right[maxn];
int pre[maxn],other[maxn],last[maxn];
LL ans;
LL cost[maxn],value[maxn],size[maxn],sum[maxn];
 
void connect(int x,int y) {
    pre[++l]=last[x];
    last[x]=l;
    other[l]=y;
}
 
int combine(int x,int y) {
    if ((!x)||(!y)) return x+y;
    if (cost[x]<cost[y]) swap(x,y);
    right[x]=combine(right[x],y);
    sum[x]=sum[left[x]]+sum[right[x]]+cost[x];
    size[x]=size[left[x]]+size[right[x]]+1;
    return x;
}
 
int work(int x) {
    sum[x]=cost[x]; size[x]=1;
    int rot=x;
    for (int p=last[x];p;p=pre[p]) rot=combine(rot,work(other[p]));
    while (sum[rot]>m) rot=combine(left[rot],right[rot]);
    ans=max(ans,value[x]*size[rot]);
    return rot;
}
 
int main() {
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) {
        int x; scanf("%d%lld%lld",&x,&cost[i],&value[i]);
        if (x) connect(x,i);
    }
    work(1);
    printf("%lld\n",ans);
    return 0;
}