给出一棵树,每个点有个点权.现在要求把树上的点划分到一些集合中,要求每个集合的任意两个点不能是祖先-儿子关系.每个集合的大小定义为其中所有点点权的最大值.求集合总大小最小能是多少.

链接

LOJ

COGS

BZOJ

题解

启发式合并.

考虑把一个节点的所有子树的节点划分出的集合进行合并,来得到该节点的子树的划分方案.每一个点建一个大根堆,表示以这个节点为根的子树的划分集合.合并时考虑使用启发式合并,小的堆并到大的堆上.总的时间复杂度为

O(nlognlogn)

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
#define N 200010
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;

int n,i,x;
int fa[N];
LL Ans;
LL m[N];

priority_queue <LL> t[N],v;
vector <int> son[N];

inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline LL Max(LL a,LL b){return (a>b)?a:b;}

inline int read(){
    int p=0;    char    c=getchar();
    while (c<48||c>57)  c=getchar();
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p;
}

inline void Dfs(int x){
    for (auto i :son[x]){
        Dfs(i);
        if (t[fa[i]].size()>t[fa[x]].size())    Swap(fa[x],fa[i]);
        while (!t[fa[i]].empty()){
            v.push(Max(t[fa[i]].top(),t[fa[x]].top()));
            t[fa[i]].pop(); t[fa[x]].pop();
        }
        while (!v.empty())  t[fa[x]].push(v.top()),v.pop();
    }
    t[fa[x]].push(m[x]);
}

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    n=read();
    for (i=1;i<=n;i++)  m[i]=read(),fa[i]=i;
    for (i=2;i<=n;i++){
        x=read();   son[x].push_back(i);
    }
    Dfs(1);
    while (!t[fa[1]].empty())   Ans+=t[fa[1]].top(),t[fa[1]].pop();
    printf("%lld\n",Ans);
    return 0;
}