题解 P5290 【[十二省联考2019]春节十二响】

· · 题解

在博客查看

大致题意： 给你一棵有n个节点的树，要求你将一个长度为n的序列划分成若干段，使得任意一段中没有两个数满足它们在树上是祖先——后代关系。请你求出每一段最大值之和的最小值。

大致思路

这题应该是比较水的一道堆的题目。

考虑到不能有祖先——后代关系，则显然，以x为根的子树内的答案，肯定要与以fa_x的其他儿子为根的子树内的答案合并。

而怎么合并呢？

假设我们当前要合并分别以x,y为根的两棵子树的答案。

一个贪心的思想，似乎<u>分别将两棵子树内的答案从大到小排序，然后再依次合并两棵子树内的答案（取较大值）</u>，就是最优的方案！

而针对多棵子树的合并，我们只要将其依次两两合并即可。

当我们合并完一个点的所有子树的答案之后，再在得到的这个答案序列中加入该点的权值，就可以得到该点的答案序列了。

最后的答案就是1号节点的答案序列中所有数之和。

正确性证明

为什么前面提到的那种合并答案的做法是正确的呢？

让我们以两个答案序列各自只有两个数x_1,x_2和y_1,y_2（x_1\ge y_1,x_1\ge x_2,y_1\ge y_2）为例（其余情况可以由此推广），因为显然尽可能多匹配肯定更优，所以只有两种配对方式：

然后对于x_1,x_2,y_1,y_2之间的大小关系，我们再进行分类讨论：

综上所述，第一种方案（即前面提到的方案）选出的答案必然为最优解。

正确性也就得到了证明（当然，肯定有更简便的证明方式，只不过我难以将其说清楚，只能采用这种举例子的方式）。

具体实现

然后我们考虑如何维护这个答案序列。

考虑到要维护其从大到小的顺序，便自然可以想到用堆来维护。

我们用一个p_i表示第i个节点的答案序列所对应的堆的编号，初始化p_i=i。

然后，每次合并x,y时，我们先比较p_x,p_y两个堆的大小，然后通过swap使得Size_{p_x}>Size_{p_y}，然后将y的答案合并给x，这样时间复杂度就可以用类似于启发式合并的方式来证明。

合并答案的过程中我们可以开一个临时数组来存下合并后的答案。

由于在两两配对完后，p_x堆中还会有一些剩下的元素，因此我们把这个临时数组中的元素再全部扔入p_x堆中，即可得到配对后的答案序列了。

一些细节可以详见代码。

代码

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define RL Reg LL
#define Con const
#define CI Con int&
#define CL Con LL&
#define I inline
#define W while
#define N 200000
#define LL long long
#define add(x,y) (e[++ee].nxt=lnk[x],e[lnk[x]=ee].to=y)
#define max(x,y) ((x)>(y)?(x):(y))
#define swap(x,y) (x^=y^=x^=y)
using namespace std;
int n,ee,a[N+5],s[N+5],p[N+5],lnk[N+5];struct edge {int to,nxt;}e[N];
priority_queue<int> q[N+5];
class FastIO
{
    private:
        #define FS 100000
        #define tc() (A==B&&(B=(A=FI)+fread(FI,1,FS,stdin),A==B)?EOF:*A++)
        #define tn (x<<3)+(x<<1)
        #define D isdigit(c=tc())
        char c,*A,*B,FI[FS];
    public:
        I FastIO() {A=B=FI;}
        Tp I void read(Ty& x) {x=0;W(!D);W(x=tn+(c&15),D);}
        Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
}F;
I void dfs(CI x)//遍历树
{
    for(RI i=lnk[p[x]=x],t;i;i=e[i].nxt)//初始化p[x]为x
    {
        dfs(e[i].to),t=0,q[p[x]].size()<q[p[e[i].to]].size()&&swap(p[x],p[e[i].to]);//处理子树，通过swap的方式使p[x]堆的Size较大
        W(!q[p[e[i].to]].empty())//将元素两两配对
            s[++t]=max(q[p[x]].top(),q[p[e[i].to]].top()),//用临时数组存下来
            q[p[x]].pop(),q[p[e[i].to]].pop();//将两个堆的堆顶弹掉
        W(t) q[p[x]].push(s[t--]);//将临时数组中的元素全部扔入p[x]堆中
    }q[p[x]].push(a[x]);//将当前节点权值扔入堆中
}
int main()
{
    RI i,x;for(F.read(n),i=1;i<=n;++i) F.read(a[i]);for(i=2;i<=n;++i) F.read(x),add(x,i);//读入+建边
    RL ans=0;dfs(1);W(!q[p[1]].empty()) ans+=q[p[1]].top(),q[p[1]].pop();//遍历+统计答案
    return printf("%lld",ans),0;//输出答案
}