Luogu5290

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

Description

你有 个程序在同一棵调用树上，每个程序有所需内存大小 和调用树上的父亲 。

你需要把所有的程序放到内存里，可以把内存分段，对于大小为 的段，它能放下所有所需内存大小不大于 的程序。

现在要求对任何一个程序它不能和任何在调用树上与它有祖先关系的程序放到同一个段里。

求最小的总内存大小使得存在一种分段并放置所有程序的方式。

。

Sol

我们设每个子树都已经计算出了最小空间以及其递减排序后分配方案 ，那么子树根的分配方案就是对于每个 取最大值。

如果不对合并加以优化，那么总时间复杂度可能高达 。

这时很容易想到启发式合并，每次总是让较小的分配方案并到较大的分配方案上，这样合并的总时间复杂度不会超过 。（不是 ，因为较小的集合在合并完成后会被直接丢弃并不会导致集合大小增大）

由于子树根必须单独开一段内存，所以为方便插入要用优先队列存方案。

时间复杂度 。

Code

#include<bits/stdc++.h>
#define pb push_back
#define int long long
const int M=5e5+5;
template<typename Tp=int>inline Tp read(){Tp x(0);int op(0);char ch=getchar();while(ch<'0'||ch>'9')op|=(ch==45),ch=getchar();while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();return op?-x:x;}
std::vector<int> G[M];
std::priority_queue<int> pq[M];
int n,a[M];
void mrg(int x,int y){
    std::vector<int> tmp;
    if(pq[x].size()<pq[y].size())std::swap(pq[x],pq[y]);
    while(!pq[y].empty()){
        tmp.pb(std::max(pq[x].top(),pq[y].top()));
        pq[x].pop(),pq[y].pop();
    }
    for(auto v:tmp)pq[x].push(v);
}
void dfs(int u){
    for(auto v:G[u])dfs(v),mrg(u,v);
    pq[u].push(a[u]);
}
signed main(){
    n=read();
    for(int i=1;i<=n;++i)a[i]=read();
    for(int i=2;i<=n;++i)G[read()].pb(i);
    dfs(1);
    int ans=0;
    while(!pq[1].empty())ans+=pq[1].top(),pq[1].pop();
    printf("%lld\n",ans);
    return 0;
}