记录编号	242065	评测结果	AAAAAAAAAAAAAAAAAAAATTTTAAAAAATTTTTTAATTAAAAAATTAAAAAATTTTTT
题目名称	796.[APIO 2012] 派遣	最终得分	66
用户昵称	TenderRun	是否通过	未通过
代码语言	C++	运行时间	9.830 s
提交时间	2016-03-26 15:07:55	内存使用	4.81 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn=100010;
long long ans=0,sum[maxn];
int n,m,cnt,fir[maxn],nxt[maxn],to[maxn];
int sup[maxn],val[maxn],lead[maxn];
int fa[maxn],ch[maxn][2],sz[maxn];
void addedge(int a,int b){
	nxt[++cnt]=fir[a];fir[a]=cnt;to[cnt]=b;
}

void Push_up(int node){
	sum[node]=sum[ch[node][0]]+sum[ch[node][1]]+val[node];
	sz[node]=sz[ch[node][0]]+sz[ch[node][1]]+1;
}

void Rotate(int x){
	int y=fa[x],g=fa[y],c=ch[y][1]==x;
	ch[y][c]=ch[x][c^1];fa[y]=x;
	ch[x][c^1]=y;fa[ch[y][c]]=y;
	fa[x]=g;
	if(g)
		ch[g][ch[g][1]==y]=x;
	Push_up(y);
}

void Splay(int x,int g=0){
	for(int y;(y=fa[x])!=g;Rotate(x))
		if(fa[y]!=g)
			Rotate((ch[fa[y]][1]==y)==(ch[y][1]==x)?y:x);
	Push_up(x);
}

void Insert(int node,int p){
	int pre;
	while(p){
		pre=p;
		sum[p]+=val[node];sz[p]++;
		p=ch[p][val[p]<val[node]];
	}
	ch[pre][val[pre]<val[node]]=node;
	ch[node][0]=ch[node][1]=0;
	fa[node]=pre;sum[node]=val[node];
	sz[node]=1;Splay(node);
	return;
}

void Merge(int node,int p){
	if(!node)return;
	int ls=ch[node][0],rs=ch[node][1];
	Merge(ls,p);
	Splay(p);
	Insert(node,p);
	Merge(rs,p);
	return;
}

int Query(int node){
	int ret=0,rem=m;
	while(node){
		if(rem>=sum[ch[node][0]]+val[node]){
			rem-=sum[ch[node][0]]+val[node];
			ret+=sz[ch[node][0]]+1;
			node=ch[node][1];
		}
		else{
			ch[node][1]=0;
			Push_up(node);
			node=ch[node][0];
		}
	}
	return ret;
}

void Solve(int node){
	for(int i=fir[node];i;i=nxt[i]){
		Solve(to[i]);
		if(sz[node]>sz[to[i]]){Merge(node,to[i]);Splay(node);}
		else{Merge(to[i],node);Splay(node);}
	}
	ans=max(ans,1ll*lead[node]*Query(node));
	return;
}

int main(){
	freopen("dispatching.in","r",stdin);
	freopen("dispatching.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d%d%d",&sup[i],&val[i],&lead[i]);
		addedge(sup[i],i);
	}
	for(int i=1;i<=n;i++)
		sz[i]=1,sum[i]=val[i];	
	Solve(1);
	printf("%lld\n",ans);
	return 0;
}