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

题目链接

题目大意

一颗有根树, 有点权, 把点分成若干个集合, 要求每个集合内不包含祖先关系, 求集合的最大值的和的最小值.

做题思路

考虑合并两个集合, 我们只需要不停把分别吧两个集合的最大值取出取max加入答案, 再把大集合剩下的内容加进答案.

通过直接使用之前的堆, 不用开新的堆, 可以做到 \(O(min(S_1,S_2))\)

我们对于每个节点, 直接合并所有子树, 然后加入这个节点单独成一个集合.

复杂度计算

我们发现, 把一个节点的所有子树合并的时间复杂度正好相当于整个子树的大小减去最大的儿子的大小.

所以,这个算法可以理解为一种树上启发式合并,时间复杂度为 \(O(n\log^2n)\) , 其中一个\(\log\)是堆,一个\(\log\)是启发式合并

核心代码

namespace WangManhe{
    using namespace Basic_Data_Structure;
    const int MxN=200000;
    
    int n;
    int head[MxN+5],nxt[2*MxN+5],to[2*MxN+5],tot;
    int siz[MxN+5],son[MxN+5];
    int cost[MxN+5],id[MxN+5];
    Heap<int>H[MxN+5];

    void AddEdge(int u,int v){
        to[++tot]=v;
        nxt[tot]=head[u];
        head[u]=tot;
    }
    void DFS1(int p,int fa){
        for(int i=head[p];i;i=nxt[i]){
            if(to[i]!=fa){
                DFS1(to[i],p);
                Heap<int>T;
                if(H[id[p]].size()<H[id[to[i]]].size()){
                    swap(id[p],id[to[i]]);
                }
                while(!H[id[to[i]]].empty()){
                    T.push(max(H[id[to[i]]].top(),H[id[p]].top()));
                    H[id[to[i]]].pop();H[id[p]].pop();
                }
                while(!T.empty()){
                    H[id[p]].push(T.top());
                    T.pop();
                }
            }
        }
        H[id[p]].push(cost[p]);
    }
    void Main(int Case){
        int u,v;
        scanf("%lld",&n);
        for(int i=1;i<=n;i++){
            scanf("%lld",&cost[i]);
            id[i]=i;
        }
        for(int i=2;i<=n;i++){
            scanf("%lld",&u);
            AddEdge(u,i);
            AddEdge(i,u);
        }
        DFS1(1,0);
        int ans=0;
        while(!H[id[1]].empty()){
            ans+=H[id[1]].top();
            H[id[1]].pop();
        }
        printf("%lld\n",ans);
    }
    void Initialize(){
        
    }
}