由題意可知，對于每個子樹內用一定費用來雇忍者使得根節點的忍者領導能力*雇傭人數最大。
對于每個子樹可以用堆來維護費用的大小，每次合并兩個子樹時，合并兩個堆就行了…..所以這里我們需要使用到可并堆。
本人碼力較低，代碼中使用的的是斜堆，個人認為比較好寫，只有一個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);新聞熱點
疑難解答
