傳送門

考慮一個子樹里是怎么劃分的，維護劃分出來的每個集合的最大值，這個可以用一個 $multiset$ 維護

設 $S[x]$ 表示節點 $x$ 的子樹中，最優劃分 劃分出來的每個塊的節點最大值

首先葉子節點的集合顯然只有它本身

然后考慮子樹之間的合并，設兩個子樹根節點為 $x,y$，因為兩個子樹之間一定不會有祖先后代關系

貪心地想，顯然 $S[x]$ 的最大值優先跟 $S[y]$ 的最大值合并（取 $max$），然后次大值跟次大值合并...這樣一路合并下去是最優的

所以直接啟發式合并就好了

$x$ 的子樹合并完后還要考慮當前節點 $x$ 也加入進來，顯然此節點只能單獨分一個塊出來

一開始以為復雜度 $O(nlog^2_n)$（啟發式合并 $nlog_n$，$multiset$ 單次操作 $log_n$）

但是經過對代碼的分析可以發現，這并不是直接合并，而是小的 $S$ 和大的取一個最大值后就沒了，并沒有增加大的集合的集合大小

所以每個節點只會算一次，復雜度 $O(nlog_n)$

#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #include<set> using namespace std; typedef long long ll; inline int read() {int x=0; char ch=getchar();while(ch<'0'||ch>'9') ch=getchar();while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }return x; } const int N=4e5+7; int fir[N],from[N<<1],to[N<<1],cntt; inline void add(int a,int b) {from[++cntt]=fir[a]; fir[a]=cntt;to[cntt]=b; } int n,val[N]; multiset <int> S[N]; multiset <int>::iterator it,pit,itt; inline void merge(int x,int y)//很多細節的啟發式合并操作 {if(S[x].size()<S[y].size()) swap(S[x],S[y]);//啟發式合并if(!S[y].size()) return;//記得特判，不然后面it--時會直接GGpit=S[x].end(); pit--; bool flag=1;it=S[y].end(); it--;while(it!=S[y].begin()){pit--; itt=pit; pit++;//注意要先用itt存一下pit-1的指針等等erase(pit)后pit就是指向不合法地址的指針了，那時再pit--就GG了if((*it)>(*pit)) S[x].erase(pit),S[x].insert(*it);it--; pit=itt;}if((*it)>(*pit)) S[x].erase(pit),S[x].insert(*it);//注意最后S[y].begin()的值還沒合并 } void dfs(int x) {for(int i=fir[x];i;i=from[i])dfs(to[i]),merge(x,to[i]);S[x].insert(val[x]); } int main() {n=read(); int a;for(int i=1;i<=n;i++) val[i]=read();for(int i=2;i<=n;i++)a=read(),add(a,i);dfs(1);ll ans=0;for(it=S[1].begin();it!=S[1].end();it++) ans+=(*it);printf("%lld",ans);return 0; }

?

轉載于:https://www.cnblogs.com/LLTYYC/p/10682961.html

總結

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

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