记录编号	170693	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[APIO 2012] 派遣	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	1.822 s
提交时间	2015-07-15 07:44:11	内存使用	5.28 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
typedef long long LL;
const int SIZEN=100010;
int N;
class NODE{//大根左偏树的结点
public:
	int l,r;
	int h;
	int val,siz;
	LL sum;
	#define l(x) tree[x].l
	#define r(x) tree[x].r
	#define h(x) tree[x].h
	#define val(x) tree[x].val
	#define siz(x) tree[x].siz
	#define sum(x) tree[x].sum
};
NODE tree[SIZEN];
int root[SIZEN]={0};
int merge(int u,int v){
	if(!u||!v) return u+v;
	if(val(u)<val(v)) swap(u,v);
	r(u)=merge(r(u),v);
	if(h(l(u))<h(r(u))) swap(l(u),r(u));
	h(u)=h(r(u))+1;
	siz(u)=siz(l(u))+siz(r(u))+1;
	sum(u)=sum(l(u))+sum(r(u))+val(u);
	return u;
}
LL MX;//预算
LL leader[SIZEN]={0};
LL ans=0;
int master;
vector<int> c[SIZEN];//存的其实是子节点
void DFS(int x){
	root[x]=x;
	l(x)=r(x)=0;
	h(x)=siz(x)=1;
	sum(x)=val(x);
	for(int i=0;i<c[x].size();i++){
		DFS(c[x][i]);
		root[x]=merge(root[x],root[c[x][i]]);
	}
	while(sum(root[x])>MX) root[x]=merge(l(root[x]),r(root[x]));//合并两个子树就是删去最大点
	ans=max(ans,leader[x]*siz(root[x]));
}
void init(void){
	scanf("%d",&N);
	scanf("%lld",&MX);
	int p;
	for(int i=1;i<=N;i++){
		scanf("%d",&p);
		scanf("%lld%lld",&val(i),&leader[i]);
		if(!p) master=i;
		c[p].push_back(i);
	}
}
int main(){
	freopen("dispatching.in","r",stdin);
	freopen("dispatching.out","w",stdout);
	init();
	DFS(master);
	printf("%lld\n",ans);
	return 0;
}