记录编号	431536	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[APIO 2012] 派遣	最终得分	100
用户昵称	ztx	是否通过	通过
代码语言	C++	运行时间	0.857 s
提交时间	2017-07-31 22:42:13	内存使用	2.60 MiB

/// by ztx
/// blog.csdn.net/hzoi_ztx
#include <bits/stdc++.h>
#define Rep(i,l,r) for(i=(l);i<=(r);i++)
#define rep(i,l,r) for(i=(l);i< (r);i++)
#define Rev(i,r,l) for(i=(r);i>=(l);i--)
#define rev(i,r,l) for(i=(r);i> (l);i--)
#define Each(i,v)  for(i=v.begin();i!=v.end();i++)
typedef long long ll ;
typedef double lf ;
int CH , NEG ;
template <typename TP>inline void read(TP& ret) {
    ret = NEG = 0 ; while (CH=getchar() , CH<'!') ;
    if (CH == '-') NEG = true , CH = getchar() ;
    while (ret = ret*10+CH-'0' , CH=getchar() , CH>'!') ;
    if (NEG) ret = -ret ;
}

#define  kN  100010LL
struct lt {
    lt *l, *r;
    int sz, w, d;
    lt();
    lt(int w);
}*null=new lt();
lt::lt() { l=r=null;w=d=sz=0; }
lt::lt(int w): w(w) { l=r=null;d=0;sz=1; }
lt* Init(int x) { return new lt(x); }
lt* Merge(lt*u,lt*v) {
    if (u == null) return v;
    if (v == null) return u;
    if (u->w < v->w) std::swap(u,v);
    u->r = Merge(u->r,v);
    if (u->l->d < u->r->d) std::swap(u->l,u->r);
    u->d = u->r->d+1;
    u->sz = u->l->sz+u->r->sz+1;
    return u;
}
void Insert(lt*&u,int x) { u = Merge(u,Init(x)); }
int Top(lt*u) { return u->w; }
void Pop(lt*&u) { lt*tmp = u; u = Merge(u->l,u->r); delete tmp; }
bool Empty(lt*u) { return u == null; }
int Size(lt*u) { return u->sz; }

int n, lim;
int fa[kN], cost[kN], lead[kN];
lt* q[kN];
ll sum[kN];

#define r(x)   read(x)
int main() {
    freopen("dispatching.in" ,"r",stdin ) ;
    freopen("dispatching.out","w",stdout) ;
    int i;
    ll tmp, ans = 0;
    r(n), r(lim);
    Rep (i,1,n)
        r(fa[i]), r(cost[i]), r(lead[i]),
        q[i] = Init(cost[i]), sum[i] = cost[i];
    Rev (i,n,1) {
        while (sum[i] > lim)
            sum[i] -= Top(q[i]), Pop(q[i]);
        if (tmp=1LL*lead[i]*Size(q[i]), tmp>ans) ans = tmp;
        if (fa[i] > 0) {
            sum[fa[i]] += sum[i];
            q[fa[i]] = Merge(q[i],q[fa[i]]);
        }
    }
    printf("%lld\n", ans);
    END: getchar(), getchar();
    return 0;
}