BZOJ 2809 Apio2012]dispatching 斜堆可并堆

2019-11-06 06:29:28

字体：大中小

来源：转载

供稿：网友

由题意可知，对于每个子树内用一定费用来雇忍者使得根节点的忍者领导能力*雇佣人数最大。

对于每个子树可以用堆来维护费用的大小，每次合并两个子树时，合并两个堆就行了…..所以这里我们需要使用到可并堆。

本人码力较低，代码中使用的的是斜堆，个人认为比较好写，只有一个merge操作，加入新节点只要合并即可，删除节点时只需把根节点的左右儿子合并。每次操作时间复杂度均摊O(nlogn)（QAQ并不会证）。

#include<cstdio>#include<vector>#include<iostream>#include<algorithm>#define ll long longusing namespace std;const int maxn = 200000;vector<int> f[maxn];int n,x,tot,rt[maxn],led[maxn]; ll c[maxn],m,ans=0;struct node{ int l,r,sz; ll sum; }a[maxn];int merge(int x,int y){ if(!x||!y) return x + y; if(c[x]<c[y]) swap(x,y); a[x].r=merge(a[x].r,y); swap(a[x].l,a[x].r); return x;}void dfs(int x){ a[x].sum=c[x];a[x].sz=1;rt[x]=x; for (int i=0;i<f[x].size();i++) { int v=f[x][i]; dfs(v); a[x].sum+=a[v].sum; a[x].sz+=a[v].sz; rt[x]=merge(rt[x],rt[v]); } while(a[x].sum>m) { a[x].sum-=c[rt[x]]; a[x].sz--; rt[x]=merge(a[rt[x]].l,a[rt[x]].r); } ans=max(ans,(ll)led[x]*a[x].sz);}int main(){ freopen("dispatching.in","r",stdin); freopen("dispatching.out","w",stdout); scanf("%d%lld",&n,&m); for(int i=1;i<=n;i++) { scanf("%d%lld%d",&x,&c[i],&led[i]); if(x) f[x].push_back(i); } dfs(1); PRintf("%lld/n",ans); return 0;}/*5 40 3 31 3 52 2 21 2 42 3 1*/

上一篇：Codeforces Round #403 The Meeting Place Cannot Be Changed(二分，三分)

下一篇：关于主席树的自学