M_sea

洛谷5290 [十二省联考2019]春节十二响
LuoguBZOJ分析先考虑一条链的情况怎么做。显然 $1$ 最多会有两条支链,那么两条支链排序后对应相加即可。正...
扫描右侧二维码阅读全文
16
2019/04

洛谷5290 [十二省联考2019]春节十二响

Luogu

BZOJ

分析

先考虑一条链的情况怎么做。

显然 $1$ 最多会有两条支链,那么两条支链排序后对应相加即可。正确性显然。

考虑把这个东西扩展到树上。每个节点维护一个堆,然后向上启发式合并即可。

时间复杂度为 $O(n\log n)$ 。

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
typedef long long ll;
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10;

struct Edge { int v,nxt; } e[N];
int head[N];
int a[N],id[N],tmp[N],tim=0;
priority_queue<int> q[N];

inline void addEdge(int u,int v) {
    static int cnt=0;
    e[++cnt]=(Edge){v,head[u]},head[u]=cnt;
}

inline void dfs(int u) {
    id[u]=++tim;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; dfs(v);
        if (q[id[u]].size()<q[id[v]].size()) swap(id[u],id[v]);
        int sz=q[id[v]].size();
        for (re int i=1;i<=sz;++i) {
            tmp[i]=max(q[id[u]].top(),q[id[v]].top());
            q[id[u]].pop(),q[id[v]].pop();
        }
        for (re int i=1;i<=sz;++i) q[id[u]].push(tmp[i]);
    }
    q[id[u]].push(a[u]);
}

int main() {
    int n=read();
    for (re int i=1;i<=n;++i) a[i]=read();
    for (re int i=2;i<=n;++i) addEdge(read(),i);
    dfs(1); ll ans=0;
    while (!q[id[1]].empty()) ans+=q[id[1]].top(),q[id[1]].pop();
    printf("%lld\n",ans);
    return 0;
}
最后修改:2019 年 05 月 26 日 09 : 39 PM

2 条评论

  1. smy

    正确性显然cao

    1. M_sea
      @smy

      拍了几十万组都是对的

发表评论