BZOJ - 2809 dispatching 主席树+dfs序

#include <bits/stdc++.h>
#define nd seg[now]
#define ndp seg[pre]
#define mid ((s+t)>>1)
#define ll long long
using namespace std;
const int maxn=1e5+10;
const int maxm=1e6+10;
const int INF=0x3f3f3f3f;
int casn,n,k;
ll m;
struct node2{
	int to,next;
}e[maxn];
int	head[maxn],nume;
int tin[maxn],tout[maxn];
ll cost[maxn],pos[maxn],power[maxn];
int rt[maxn],size,cnt,pre[maxn],dfn[maxn];
int cmp(int a,int b){
	return cost[a]<cost[b];
}
inline void add(int a,int b){
	e[++nume]=(node2){b,head[a]};
	head[a]=nume;
}
void dfs(int now){
	tin[now]=++cnt;
	dfn[cnt]=now;
	for(int i=head[now];i;i=e[i].next){
		dfs(e[i].to);
	}
	tout[now]=cnt;
}
struct node{
	int l,r;ll sum,cnt;
}seg[maxn*20];
void maketree(int s=1,int t=n,int &now=rt[0]){
	now=++size;nd=(node){s,t,0,0};
	if(s==t) return ;
	maketree(s,mid,nd.l);maketree(mid+1,t,nd.r);
}
void update(int &now,int pre,int k,ll cost,int s=1,int t=n){
	now=++size;nd=ndp,nd.sum+=cost,nd.cnt++;
	if(s==t) return ;
	if(k<=mid)update(nd.l,ndp.l,k,cost,s,mid);
	else update(nd.r,ndp.r,k,cost,mid+1,t);
}
ll query(int ndl,int ndr,ll k,int s=1,int t=n){
	if(seg[ndr].sum-seg[ndl].sum<=k) return seg[ndr].cnt-seg[ndl].cnt;
	if(s==t) return min(seg[ndr].cnt-seg[ndl].cnt,k/pos[s]);
	ll sum=seg[seg[ndr].l].sum-seg[seg[ndl].l].sum;
	if(k>=sum) return query(seg[ndl].r,seg[ndr].r,k-sum,mid+1,t)+seg[seg[ndr].l].cnt-seg[seg[ndl].l].cnt;
	else return query(seg[ndl].l,seg[ndr].l,k,s,mid);
}
#undef mid
int main(){
	scanf("%d%lld",&k,&m);
	int master;
	for(int i=1;i<=k;i++){
		scanf("%d%lld%lld",pre+i,cost+i,power+i);
		if(pre[i]==0)master=i;
		else add(pre[i],i);
		pos[i]=cost[i];
	}
	sort(pos+1,pos+1+k);
	n=unique(pos+1,pos+1+k)-(pos+1);
	dfs(master);
	maketree();
	for(int i=1;i<=k;i++){
		int id=lower_bound(pos+1,pos+1+n,cost[dfn[i]])-pos;
		update(rt[i],rt[i-1],id,cost[dfn[i]]);
	}
	ll ans=0;
	for(int i=1;i<=k;i++){
		ans=max(ans,power[i]*query(rt[tin[i]-1],rt[tout[i]],m));
	}
	printf("%lld\n",ans);
  return 0;
}