洛谷 P5290 【十二省联考2019】春节十二响题解

2020-2-26 xiaoh

题意

给定一棵以 $1$ 为根,有 $n$ 个节点的树( $1\leq n\leq 2\times 10^5$ ),第 $i$ 个点有一个权值 $s_i$ ( $1\leq s_i\leq 10^9$ ).对于不是祖先-后代关系的点,我们可以把它们放在一个集合中.一个集合的大小为其中权值最大的点的点权.你可以将所有的点划分成任意多个集合,但每个集合中所有点必须两两满足上述条件.求所有集合总大小的最小值

题解

不难发现,当两个集合并为一个集合的时候,总代价会变小,且相同情况下集合的大小越小总大小越小.所以对于每一个确定了最大值的集合,我们要尽可能的去带走它的前驱,前驱的前驱,……(前提是不违背题意中的限制)所以本题大致确定可以使用贪心的方法.
先考虑整棵树是一条链的时候,那么我们可以把整个左儿子和右儿子分别建成一个大根堆,每次取堆顶元素构成集合,当某一个堆取完时,剩下的元素和根自己构成一个集合.不难证明这个是最优的.我们考虑怎样将其拓展到树上.考虑对于每一个节点都建一个堆,表示以这个节点为根的子树按照上述的最优策略所构成的子所有集合的集合大小.那么假设一个节点有两个儿子,那么我们可以对这两个儿子进行与链相同的操作,不难证明这是最优的.而对于多叉树,很明显每次合并两个,多合并几次就合并完了嘛.但是这样,我们的复杂度依旧是停留在 $O(n^2\log n)$ 级别的,原因就在于合并的复杂度为两个堆的 $size$ 中较大的那个.那怎么样能进行优化呢?我们想到了启发式合并.每次合并都将小的堆往大的堆合并,这样复杂度就降为了 $O(n\log n)$ .当然很多人认为这道题的复杂度是 $O(n\log^2n)$ 的,实际上呢,我们可以将合并理解为删除小的子树,因此至多进行合并 $n$ 次.所以总的复杂度为 $O(n\log n)$ .

Code

#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x)
{
	x=0;
	int f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
}
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	x*=f;
	return;
}	
template<typename T>
void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
	return;
}
const int MAXN=200010;
int n;
long long a[MAXN];
int tot=1;
int edge[MAXN],nxt[MAXN],hd[MAXN];
inline void add_edge(int u,int v)
{
    edge[tot]=v,nxt[tot]=hd[u],hd[u]=tot++;
}
int ch[MAXN][2],sz[MAXN],dis[MAXN];//笔者在此使用了左偏树来实现
long long val[MAXN];
int merge(int a,int b)//合并
{
    if(!a||!b) return a+b;
    if(val[a]<val[b]) swap(a,b);
    ch[a][1]=merge(ch[a][1],b);
    if(dis[ch[a][0]]<dis[ch[a][1]]) swap(ch[a][0],ch[a][1]);
    dis[a]=dis[ch[a][1]]+1;
    sz[a]=sz[ch[a][0]]+sz[ch[a][1]]+1;
    return a;
}
inline long long pop(int &p)//弹出
{
    int x=p;
    p=merge(ch[p][0],ch[p][1]);
    ch[x][0]=ch[x][1]=0,sz[x]=1;
    return val[x];
}
queue<int> q;
inline void Union(int &x,int y)//按照贪心的原则合并两棵左偏树
{
    if(sz[x]<sz[y]) swap(x,y);
    while(!q.empty()) q.pop();
    while(sz[y])
    {
        if(val[x]<val[y]) q.push(y);
        else q.push(x);
        pop(x),pop(y);
    }
    while(!q.empty()) x=merge(x,q.front()),q.pop();
}
int dfs(int p)//dfs遍历整棵树并求解
{
    int tmp=0;
    for(int i=hd[p];i;i=nxt[i]) Union(tmp,dfs(edge[i]));
    tmp=merge(tmp,p);
    return tmp;
}
long long ans=0;
int main()
{
    read(n);
    for(int i=1;i<=n;i++) read(a[i]),val[i]=a[i],sz[i]=1;
    for(int i=2;i<=n;i++)
    {
        int fa;
        read(fa);
        add_edge(fa,i);
    }
    int rt=dfs(1);
    while(sz[rt]) ans+=pop(rt);
    write(ans),putchar('\n');
	return 0;
}

后记

本人的第一道 $AC$ 的黑题,值得好好庆祝一下(虽然是看了题解才想出来的QAQ)