省选专练APIO2012派遣

首先给了一个树。

求出这一棵树上某子树的为权值*k个sum和小于m的数最大是多少。

算法一

• 枚举一个点x作为管理者

• 计算x的后代集合，并按照C i 从小到大排序

• 按照C i 依次取节点使得薪水之和不超过M ， 得到S.

• 计算L x ×|S|，取最大值.

时间复杂度: O(N^2 logN)

期望得分 ：  ≤ 30

算法二

• 基于算法一

• 初始将所有节点按照C i  排序

• 每次枚举点x的后代，直接利用桶排代替快排

• 时间复杂度: O(N^2 )

• 期望得分：30 ~ 50

算法三

• 考虑两个节点 x 和 y, x 是 y 的父亲，对于y的后代z，可以发现

如果在y是管理者的时候z不被选中，那么在 x 是管理者的时候z

一定不会被选中

• 对于每个节点维护哪些后代被选中，并按照C i 排序

• 对于每个节点x, 将它的孩子节点的选择集合加上x作归并排序，

并且选取前若干个作为x的选择集合

• 时间复杂度：O(N^2 )

• 期望得分：30 ~ 50

算法四

• 基于算法三

• 对于每一个节点的选择集合用 二叉堆来维护，需要维护两

个堆的合并.

• 堆的合并：每次将节点少的堆中的节点逐个插入到节点多

的堆中.

• 时间复杂度：O(Nlog*2^N)

• 期望得分：80 ~ 100

算法五

• 基于算法三

• 对于每一个节点的选择集合用 左偏树来维护，每次合并两

个堆的时间复杂度为O(logN).

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N=(int)2e6+100; 
struct Node{
	int fa,c,val;
}a[N];
void add(int fa,int c,int val,int idx){
	a[idx].fa=fa;
	a[idx].c=c;
	a[idx].val=val;
}
int n,m;
long long ans=0;
int siz[N]={0};
int root[N]={0};
int sum[N]={0}; 
void Build_Heap(int idx){
	siz[idx]=1;
	root[idx]=idx;
	sum[idx]=a[idx].c;
}
int dis[N]={0};
int lson[N]={0};
int rson[N]={0};
int merge(int A,int B){
	if(!A||!B){
		return A+B;
	}
	if(a[A].c<a[B].c){
		swap(A,B);
	}
	rson[A]=merge(rson[A],B);
	if(dis[lson[A]]<dis[rson[A]]){
		swap(lson[A],rson[A]);
	}
	dis[A]=dis[rson[A]]+1;
	return A;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		int fa,c,val;
		scanf("%d%d%d",&fa,&c,&val);
		add(fa,c,val,i);
		if(c<val)
			ans=max(ans,(long long)val);
		Build_Heap(i);
	}
	for(int i=n;i>1;i--){
		int fa=a[i].fa;
		root[fa]=merge(root[i],root[fa]);
		siz[fa]+=siz[i];
		sum[fa]+=sum[i];
		while(sum[fa]>m){
			sum[fa]-=a[root[fa]].c;
			root[fa]=merge(lson[root[fa]],rson[root[fa]]);
			siz[fa]--;
		}
		ans=max(ans,(long long)a[fa].val*(long long)siz[fa]);
	}
	cout<<ans;
}