记录编号	242157	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	796.[APIO 2012] 派遣	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	1.652 s
提交时间	2016-03-26 17:12:55	内存使用	5.65 MiB

#include<cstdio>
#include<vector>
using namespace std;
const int SIZEN=100010;
typedef long long LL;
vector<int> s[SIZEN];
class miku//大♂根左偏树
{
public:
	int l,r;
	LL val;
	LL sum;
	int siz;
	int h;
	miku()
	{
		l=r=0;
		h=0;
	}
	#define l(x) tr[x].l
	#define r(x) tr[x].r
	#define sum(x) tr[x].sum
	#define val(x) tr[x].val
	#define siz(x) tr[x].siz
	#define h(x) tr[x].h
};
miku tr[SIZEN];
int N;
LL M;
LL L[SIZEN];
LL ans=0;
int root;
int f[SIZEN];
void read()
{
	scanf("%d%lld",&N,&M);
	int p;
	for(int i=1;i<=N;i++)
	{
		scanf("%d",&p);
		scanf("%lld%lld",&val(i),&L[i]);
		if(!p) root=i;
		else s[p].push_back(i);
	}
}
int merge(int x,int y)
{
	if(!x) return y;
	if(!y) return x;
	if(val(x)<val(y)) swap(x,y);
	r(x)=merge(r(x),y);
	if(h(l(x))<h(r(x))) swap(l(x),r(x));
	h(x)=h(r(x))+1;
	siz(x)=siz(r(x))+siz(l(x))+1;
	sum(x)=sum(r(x))+sum(l(x))+val(x);
	return x;
}
void DFS(int x)
{
	f[x]=x;
	l(x)=r(x)=0;
	h(x)=siz(x)=1;
	sum(x)=val(x);
	for(int i=0;i<s[x].size();i++)
	{
		int v=s[x][i];
		DFS(v);
		f[x]=merge(f[x],f[s[x][i]]);
	}
	while(sum(f[x])>M) f[x]=merge(l(f[x]),r(f[x]));
	ans=max(ans,L[x]*siz(f[x]));
}
void work()
{
	DFS(root);
	printf("%lld",ans);
}
int main()
{
	freopen("dispatching.in","r",stdin);
	freopen("dispatching.out","w",stdout);
	read();
	work();
	return 0;
}