Qiuly

「十二省联考2019」春节十二响 堆+启发式合并 luoguP5290
要是我不是 $\texttt{HN}$ 的该多好,今年十二省联考两道傻逼题,一道异或粽子,一道十二响......[...
扫描右侧二维码阅读全文
24
2019/05

「十二省联考2019」春节十二响 堆+启发式合并 luoguP5290

要是我不是 $\texttt{HN}$ 的该多好,今年十二省联考两道傻逼题,一道异或粽子,一道十二响......

[十二省联考2019]春节十二响,启发式合并裸题。对于树中的一个节点 $u$ ,从其子树中选择一段的方式显然只能是从 $u$ 的所有子树中各选出一个节点。于是我们每一个节点开一个堆,存的就是其子树中(包括自己)的所有段的内存。

然后从下往上启发式合并即可,复杂度大约是 $O(nlogn)$ 。

启发式合并的具体代码实现如下:

void merge(int x, int y) {
    if(q[x].size()<q[y].size()) swap(q[x],q[y]);
    while(!q[y].empty()) {
        hep.push_back(max(q[x].top(),q[y].top()));
        q[x].pop(),q[y].pop();
        /*贪心选取*/
    }
    while(hep.size()) q[x].push(hep.back()),hep.pop_back();
    /*更新节点*/
}

void solve(int x) {
    for(int i=0,sz=G[x].size();i<sz;++i)
        solve(G[x][i]),merge(x,G[x][i]);/*将当前子树与之前枚举过的子树合并*/
    q[x].push(s[x]);
}

最后的总代码长度不超过 $40$ 行。

Code:

#include <queue>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N=2e5+7;

int n,f,s[N];
vector<int> hep,G[N];
priority_queue<int> q[N];

void merge(int x, int y) {
    if(q[x].size()<q[y].size()) swap(q[x],q[y]);
    while(!q[y].empty()) {
        hep.push_back(max(q[x].top(),q[y].top()));
        q[x].pop(),q[y].pop();
    }
    while(hep.size()) q[x].push(hep.back()),hep.pop_back();
}

void solve(int x) {
    for(int i=0,sz=G[x].size();i<sz;++i)
        solve(G[x][i]),merge(x,G[x][i]);
    q[x].push(s[x]);
}

int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d",&s[i]);
    for(int i=2;i<=n;++i) scanf("%d",&f),G[f].push_back(i);
    solve(1);
    long long ans=0;
    while(!q[1].empty()) ans+=q[1].top(),q[1].pop();
    printf("%lld\n",ans);
    return 0;
}
最后修改:2019 年 05 月 30 日 03 : 22 PM

发表评论