[十二省联考2019]春节十二响

佚名 6年前 (2019-04-08) 随笔 875人围观抢沙发百度已收录

题目

好像考场上稍微想一下就是正解了

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

首先看看具有启发性的链

先来说一说的我的思博贪心

我们把这条链上的点分成在\(1\)的左边还是右边，左右两边都用一个\(set\)来维护

之后我们将权值整体排序，每次拿出最大的那一个点来，去对面的链上找一个不大于它的最大的点，删掉对面的这个点

看起来非常假，但是其实是对的，因为本质上就是将两条链上的最大的和最大的，次大的和次大的...\(k\)大的和\(k\)的顺次合并

再来考虑一下由链扩展的树的情况

我们发现我们如果已经处理出了一棵子树里的最优合并情况，那么这棵子树去和他父亲的其他儿子合并的本质上就是按照刚才的方式合并两条链

于是我们开一个大根堆，启发式合并一下，把最大的和最大的，次大的和次打的，\(k\)大的和\(k\)大的合并起来，直到一个子树全部合并了为止

于是我们启发式合并一下就好了

代码，真的很好写

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#define re register
#define LL long long
#define max(a,b) ((a)>(b)?(a):(b))
const int maxn=200005;
inline int read() {
    char c=getchar();int x=0;while(c<'0'||x>'9') c=getchar();
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
struct E{int v,nxt;}e[maxn];
int head[maxn],n,num,top;
int a[maxn],st[maxn];
inline void add(int x,int y) {
    e[++num].v=y;e[num].nxt=head[x];head[x]=num;
}
std::priority_queue<int> q[maxn];
void merge(int a,int b) {
    if(q[a].size()>q[b].size()) std::swap(q[a],q[b]);
    top=0;
    while(!q[a].empty()) {
        int k=max(q[a].top(),q[b].top());
        q[a].pop();q[b].pop();
        st[++top]=k;
    }
    while(top) q[b].push(st[top--]);
}
void dfs(int x) {
    for(re int i=head[x];i;i=e[i].nxt) {
        dfs(e[i].v);
        merge(e[i].v,x);
    }
    q[x].push(a[x]);
}
int main() {
    n=read();
    for(re int i=1;i<=n;i++) a[i]=read();
    for(re int x,i=2;i<=n;i++) x=read(),add(x,i);
    dfs(1);
    LL ans=0;
    while(!q[1].empty()) ans+=q[1].top(),q[1].pop();
    printf("%lld\n",ans);
    return 0;
}