记录编号	469398	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[APIO 2012] 派遣	最终得分	100
用户昵称	Hzoi_Mafia	是否通过	通过
代码语言	C++	运行时间	1.273 s
提交时间	2017-11-03 08:46:59	内存使用	1.84 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
#define int long long
inline int read(){
	int sum(0);char ch(getchar());
	for(;ch<'0'||ch>'9';ch=getchar());
	for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
	return sum;
}
#define get_dis(x) (x?x->dis:-1)
#define get_sum(x) (x?x->sum:0)
#define get_size(x) (x?x->size:0)
struct node{
	node *lch,*rch;
	int key,sum,dis,size;
	node(int x=0):lch(NULL),rch(NULL),key(x),sum(x),dis(0),size(1){}
	inline void pushup(){
		if(get_dis(this->lch)<get_dis(this->rch))
			swap(this->lch,this->rch);
		this->dis=get_dis(this->rch)+1;
		this->size=get_size(this->lch)+get_size(this->rch)+1;
		this->sum=get_sum(this->lch)+get_sum(this->rch)+this->key;
	}
}*heap[100005];
inline node* merge(node *&x,node *&y){
	if(!x)return y;if(!y)return x;
	if(x->key<y->key)swap(x,y);
	x->rch=merge(x->rch,y);
	x->pushup();
	return x;
}
inline void insert(node *&x,int v){
	node *tmp(new node(v));
	x=merge(x,tmp);
}
inline node* pop(node *&x){
	if(!x)return NULL;
	return merge(x->lch,x->rch);
}
struct edge{
	int e;
	edge *n;
}*pre[100005];
inline void insert(int s,int e){
	edge *tmp(new edge);
	tmp->e=e;tmp->n=pre[s];pre[s]=tmp;
}
int n,m,root;
long long ans,l[100005];
inline void dfs(int u){
	for(edge *i=pre[u];i;i=i->n){
		int e(i->e);dfs(e);
		heap[u]=merge(heap[u],heap[e]);
	}
	while(heap[u]&&heap[u]->sum>m)
		heap[u]=pop(heap[u]);
	ans=max(ans,1ll*get_size(heap[u])*l[u]);
}
signed main(){
	freopen("dispatching.in","r",stdin);freopen("dispatching.out","w",stdout);
	n=read(),m=read();
	for(int i=1;i<=n;++i){
		int x(read()),y(read()),z(read());
		if(!x)root=i;
		else insert(x,i);
		insert(heap[i],y);l[i]=z;
	}
	dfs(root);printf("%lld",ans);
}