题解 P5290 【[十二省联考2019]春节十二响】
TopCarry
2019-04-07 22:06:37
## 启发式合并并不是$O(nlog^2n)$,而是$O(nlogn)$。
####
  做法：由链的部分分可以发现，对于一条链可以直接对于左右各开一个堆，然后每次左右各弹一个取$max$,我们思考怎么由链拓宽到树上。
  以二叉树为例，它的每一个二叉可以看做一条链，左右两部分按照部分分的方式合并之后就变成了条新的链，链上每个点为之前两条“子链”的两个对应点的$max$,然后递归的做下去就好了。
  至于多叉树，显然和二叉树一样。
#### 时间复杂度
  发下来的$solution$以及楼上的题解中都有提到，认为它是$log^2$,但是请注意，这道题和传统的启发式合并并不一样，因为它并没有“合并”进去，而是把小的那部分“贴”上去后直接把小的“丢掉了”，每个点只会被遍历一次，而每弹出一个点是$log$的，所以总时间复杂度是$O(nlogn)$。
```cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
static char buf[100000],*pa,*pd;
#define gc pa==pd&&(pd=(pa=buf)+fread(buf,1,100000,stdin),pa==pd)?EOF:*pa++
inline int read(){
register int x(0),f(1);register char c(gc);
while(c>'9'||c<'0')f=c=='-'?-1:1,c=gc;
while(c>='0'&&c<='9')x=x*10+c-48,c=gc;
return f*x;
}
const int N=1100000;
struct edge{
int to,next;
}e[N];
int head[N],tot;
void add(int x,int y){
e[++tot].next=head[x];e[tot].to=y;head[x]=tot;
}
#define ll long long
ll ans,val[N];
int n,po[N];
priority_queue<ll> son[N];
ll now[N];
int cnt;
void dfs(int u){
po[u]=u;
for(int i=head[u];i;i=e[i].next){
dfs(e[i].to);
if(i==head[u]){
po[u]=po[e[i].to];
}
else{
if(son[po[u]].size()<son[po[e[i].to]].size())swap(po[u],po[e[i].to]);
cnt=0;
while(!son[po[e[i].to]].empty()){
now[++cnt]=max(son[po[e[i].to]].top(),son[po[u]].top());son[po[u]].pop();son[po[e[i].to]].pop();
}
for(int j=1;j<=cnt;j++)
son[po[u]].push(now[j]);
}
}
son[po[u]].push(val[u]);
}
int main(){
freopen("spring.in","r",stdin);
freopen("spring.out","w",stdout);
n=read();
register int i;
for(i=1;i<=n;i++)val[i]=read();
for(i=2;i<=n;i++){
int fa=read();add(fa,i);
}
dfs(1);
while(!son[po[1]].empty()){
ans+=son[po[1]].top();son[po[1]].pop();
}
cout<<ans;
return 0;
}
```