记录编号	431347	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	796.[APIO 2012] 派遣	最终得分	100
用户昵称	ztx	是否通过	通过
代码语言	C++	运行时间	0.835 s
提交时间	2017-07-31 16:48:08	内存使用	4.51 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

int tot = 0, w[kN], l[kN], r[kN], d[kN], sz[kN];
int Init(int x) {
    w[++tot] = x, sz[tot] = 1, l[tot] = r[tot] = d[tot] = 0;
    return tot;
}
int Merge(int u,int v) {
    if (!u) return v;
    if (!v) return u;
    if (w[u] < w[v]) std::swap(u,v);
    r[u] = Merge(r[u],v);
    if (d[l[u]] < d[r[u]]) std::swap(l[u],r[u]);
    d[u] = d[r[u]]+1;
    sz[u] = sz[l[u]]+sz[r[u]]+1;
    return u;
}
int Insert(int u,int x) { return Merge(u,Init(x)); }
int Top(int u) { return w[u]; }
int Pop(int u) { return Merge(l[u],r[u]); }
int Size(int u) { return sz[u]; }

int n, lim;
int fa[kN], cost[kN], lead[kN], 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]), 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;
}