正題

題目鏈接:https://www.luogu.org/problemnew/show/P5290

---

題目大意

將一棵樹的所有節點分城若干個組。每個組的價格是這個組中價格最大的點，要求這個組中沒有任何祖孫關系。
求所有組的權值和最小。(1號為根節點)

---

解題思路

我們先想$10,11,12$的點(1號節點最多有兩條支鏈)。

我們可以將兩條鏈分成兩個組，然后每次取兩個組中最大的兩個進行合并。

那如果有多條支鏈但是這些支鏈不重合呢？那么我們可以將前兩個合并好之后繼續用現在的來合并后面的，因為這樣一定不會重合。

那如果支鏈重合呢？那么我們假設一個節點的所有子節點都合并好了，那么我們是不是就可以用上面的方法得出這個點，然后繼續用來求父節點。

我們可以將每個點開一個堆，然后從子節點合并給父節點。時間復雜度$O(n^{2}logn)$顯然無法勝任本題，但我們可以每次合并的時候將小的堆合并到大的堆(啟發式合并)，那么時間就會被優化到$O(nlo{g}^{2}n)$(每個點最多被合并$logn$次)

---

$code$

#include<cstdio> #include<queue> #include<algorithm> #define ll long long using namespace std; const ll N=2e5+10; struct node{ll to,next; }a[N]; ll ls[N],tot,ans,w[N],id[N],cnt,tmp[N],n; priority_queue<ll> d[N]; void addl(ll x,ll y) {a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot; } void count_ans(ll x) {id[x]=++cnt;for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to;count_ans(y);if(d[id[y]].size()>d[id[x]].size()) swap(id[x],id[y]);ll len=d[id[y]].size();for(ll i=1;i<=len;i++){tmp[i]=max(d[id[x]].top(),d[id[y]].top());d[id[x]].pop();d[id[y]].pop();}for(ll i=1;i<=len;i++)d[id[x]].push(tmp[i]);}d[id[x]].push(w[x]); } int main() {scanf("%lld",&n);for(ll i=1;i<=n;i++)scanf("%lld",&w[i]);for(ll i=2;i<=n;i++){ll x;scanf("%lld",&x);addl(x,i);}count_ans(1);while(!d[id[1]].empty())ans+=d[id[1]].top(),d[id[1]].pop();printf("%lld",ans); }

總結

以上是生活随笔為你收集整理的P5290-[十二省联考2019]春节十二响【贪心,堆】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。