【BZOJ5499】[2019省队联测]春节十二响（贪心）

时间：2022-06-09 13:28:00

【BZOJ5499】[2019省队联测]春节十二响（贪心）

题面

BZOJ

洛谷

题解

如果是一条折链，显然维护两侧的值，每次两个堆分别弹出一个\(max\)然后合并一下，最后再放回去就可以了。

那么现在回到一棵树上，可以认为就是本身有一条链，现在每次要合并一条链进来，那么拿一个堆维护这个合并过程就可以了。为了保证复杂度用启发式合并。

在\(C++11\)下可以直接使用\(.swap()\)函数来进行优先队列的交换。

为了在\(BZOJ\)上过就写的普通的启发式合并。

#include<cstdio>

#include<vector>

#include<queue>

using namespace std;

#define MAX 200200

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

int n,M[MAX];long long ans;

priority_queue<int> S[MAX];

struct Line{int v,next;}e[MAX];

int h[MAX],cnt=1;

inline void Add(int u,int v){e[cnt]=(Line){v,h[u]};h[u]=cnt++;}

int ID[MAX];

void dfs(int u)

{

	ID[u]=u;

	for(int i=h[u];i;i=e[i].next)

	{

		int v=e[i].v;dfs(v);

		if(S[ID[v]].size()>S[ID[u]].size())swap(ID[u],ID[v]);

		vector<int> tmp;

		while(!S[ID[v]].empty())tmp.push_back(max(S[ID[u]].top(),S[ID[v]].top())),S[ID[u]].pop(),S[ID[v]].pop();

		while(!tmp.empty())S[ID[u]].push(tmp.back()),tmp.pop_back();

	}

	S[ID[u]].push(M[u]);

}

/*

void dfs(int u)

{

	for(int i=h[u];i;i=e[i].next)

	{

		int v=e[i].v;dfs(v);

		if(S[v].size()>S[u].size())S[u].swap(S[v]);

		vector<int> tmp;

		while(!S[v].empty())tmp.push_back(max(S[u].top(),S[v].top())),S[u].pop(),S[v].pop();

		while(!tmp.empty())S[u].push(tmp.back()),tmp.pop_back();

	}

	S[u].push(M[u]);

}

*/

int main()

{

	n=read();

	for(int i=1;i<=n;++i)M[i]=read();

	for(int i=2;i<=n;++i)Add(read(),i);

	dfs(1);

	while(!S[ID[1]].empty())ans+=S[ID[1]].top(),S[ID[1]].pop();

	printf("%lld\n",ans);

	return 0;

}

相关文章