传送门

主席树经典题。

首先把树搞出来，然后搞出来DFS序。然后离散化点权，在DFS序上建立主席树。

对于每个点对应的区间，查找对应的区间最大的点数即可。

//BZOJ2809//by Cydiater//2016.12.6#include <iostream>#include <cstdlib>#include <cstdio>#include <cstring>#include <string>#include <algorithm>#include <queue>#include <map>#include <ctime>#include <cmath>#include <iomanip>#include <bitset>#include <set>using namespace std;#define ll long long#define up(i,j,n)		for(int i=j;i<=n;i++)#define down(i,j,n)		for(int i=j;i>=n;i--)#define cmax(a,b)		a=max(a,b)#define cmin(a,b)		a=min(a,b)#define Auto(i,node)		for(int i=LINK[node];i;i=e[i].next)#define FILE "dispatching"const int MAXN=1e5+5;const ll oo=1LL<<55;inline int read(){	char ch=getchar();int x=0,f=1;	while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();}	while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}	return x*f;}int N,root[MAXN],cnt=0,siz[MAXN],dfn[MAXN],dfs_clock=0;ll M,va[MAXN],vb[MAXN],fsort[MAXN],rnum,val[MAXN],ans=0;struct Graph{	int LINK[MAXN],len;	struct edge{		int y,next;	}e[MAXN<<1];	inline void insert(int x,int y){e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;}	inline void Insert(int x,int y){insert(x,y);insert(y,x);}	void make_graph(){		up(i,1,N){			int fa=read();va[i]=read();vb[i]=read();			fsort[i]=va[i];			if(!fa)continue;			Insert(i,fa);		}	}	void dfs(int node,int father){		siz[node]=1;dfn[++dfs_clock]=node;		Auto(i,node)if(e[i].y!=father){			dfs(e[i].y,node);			siz[node]+=siz[e[i].y];		}	}}G;struct Chair_man_Tree{	ll cost,sum;	int son[2];}t[MAXN<<5];namespace solution{	void init(){		N=read();M=read();		G.make_graph();		G.dfs(1,0);	}	int NewNode(ll cost,int sum,int son0,int son1){		t[++cnt].cost=cost;t[cnt].sum=sum;		t[cnt].son[0]=son0;t[cnt].son[1]=son1;		return cnt;	}	void insert(int leftt,int rightt,int &Root,int last,int pos){		Root=NewNode(t[last].cost+fsort[pos],t[last].sum+1,t[last].son[0],t[last].son[1]);		int mid=(leftt+rightt)>>1;		if(leftt==rightt)	return;		if(pos<=mid)		insert(leftt,mid,t[Root].son[0],t[last].son[0],pos);		else			insert(mid+1,rightt,t[Root].son[1],t[last].son[1],pos);	}	ll Get(int S,int T,int leftt,int rightt,ll LIM){		if(leftt==rightt)		return min(LIM/fsort[leftt],t[T].sum-t[S].sum);		int mid=(leftt+rightt)>>1;		ll cost=t[t[T].son[0]].cost-t[t[S].son[0]].cost;		if(cost<=LIM)	return t[t[T].son[0]].sum-t[t[S].son[0]].sum+Get(t[S].son[1],t[T].son[1],mid+1,rightt,LIM-cost);		else		return Get(t[S].son[0],t[T].son[0],leftt,mid,LIM);	}	void slove(){		sort(fsort+1,fsort+N+1);		rnum=unique(fsort+1,fsort+N+1)-(fsort+1);		up(i,1,N)val[i]=lower_bound(fsort+1,fsort+rnum+1,va[dfn[i]])-fsort;		up(i,1,N)insert(1,rnum,root[i],root[i-1],val[i]);		up(i,1,N){			int L=i,R=i+siz[dfn[i]]-1;			cmax(ans,vb[dfn[i]]*Get(root[L-1],root[R],1,rnum,M));		}		}	void output(){		cout<<ans<<endl;	}}int main(){	//freopen("input.in","r",stdin);	//freopen(FILE".in","r",stdin);	//freopen(FILE".out","w",stdout);	using namespace solution;	init();	slove();	output();	return 0;}

BZOJ2809: [Apio2012]dispatching