[APIO2012]派遣
枫林晚
2018-07-26 14:52:17
博客地址：https://www.cnblogs.com/Miracevin/p/9368414.html
n个点组成一棵树，每个点都有一个领导力和费用，可以让一个点当领导，然后在这个点的子树中选择一些费用之和不超过m的点，得到领导的领导力乘选择的点的个数（领导可不被选择）的利润。求利润最大值。
n≤100000 ；
从叶子节点开始，每个点开始是一个大根堆，堆里的就是这个点的人。
往父亲那里合并堆，记录堆的大小，费用的总和。
从儿子合并完毕后，在每个节点，不断踢出费用最大的人，直到费用的总和<=m 这就是这个点的最优方案了。（显然，花费最小的都留下了）
对于每个点，用这个点的领导力乘堆的大小尝试更新答案即可。
注意：和子树合并的时候,rt[x]=mer(rt[x],rt[y]) 注意是rt[y]因为这才是y的所属堆的入口。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100000+10;
int n;
ll m;
ll c[N],p[N];
int rt[N];
ll siz[N];
ll ans;
struct node{
int nxt,to;
}e[2*N];
int hd[N],cnt;
void add(int x,int y){
e[++cnt].nxt=hd[x];
e[cnt].to=y;
hd[x]=cnt;
}
struct tr{
int ls,rs,d;
ll cos;
ll sum,siz;
}z[N];
void pushup(int x){
z[x].sum=z[z[x].ls].sum+z[z[x].rs].sum+z[x].cos;
z[x].siz=z[z[x].ls].siz+z[z[x].rs].siz+1;
}
int mer(int x,int y){
if(!x||!y) return x+y;
if(z[x].cos<z[y].cos) swap(x,y);
z[x].rs=mer(z[x].rs,y);
if(z[z[x].ls].d<z[z[x].rs].d) swap(z[x].ls,z[x].rs);
z[x].d=z[z[x].rs].d+1;
pushup(x);
return x;
}
int split(int x){
return mer(z[x].ls,z[x].rs);
}
void dfs(int x,int fa){
z[x].cos=c[x];
z[x].ls=z[x].rs=0;z[x].siz=1;
z[x].sum=c[x];
rt[x]=x;
for(int i=hd[x];i;i=e[i].nxt){
int y=e[i].to;
if(y==fa) continue;
dfs(y,x);
rt[x]=mer(rt[x],rt[y]);//注意rt[y]
}
while(z[rt[x]].sum>m&&z[rt[x]].siz){
rt[x]=split(rt[x]);
}
ans=max(ans,z[rt[x]].siz*p[x]);
}
int main()
{
scanf("%d%lld",&n,&m);
int fa;
for(int i=1;i<=n;i++){
scanf("%d%lld%lld",&fa,&c[i],&p[i]);
add(fa,i);add(i,fa);
}
dfs(1,0);
printf("%lld",ans);
return 0;
}
```