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

原题传送门

每个点维护一个堆，表示这个点及其子树所需的每段内存的空间

搜索时从下向上做启发式合并堆中信息，最后根节点堆中所有内存空间之和就是答案

#include <bits/stdc++.h>

#define N 200005

#define ll long long

#define getchar nc

using namespace std;

inline char nc(){

    static char buf[100000],*p1=buf,*p2=buf;

    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;

}

inline int read()

{

    register int x=0,f=1;register char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

    return x*f;

}

inline void write(register ll x)

{

    if(!x)putchar('0');if(x<0)x=-x,putchar('-');

    static int sta[20];register int tot=0;

    while(x)sta[tot++]=x%10,x/=10;

    while(tot)putchar(sta[--tot]+48);

}

inline int Max(register int a,register int b)

{

	return a>b?a:b;

}

struct node{

	int to,next;

}e[N<<1];

int head[N],cnt;

inline void add(register int u,register int v)

{

	e[++cnt]=(node){v,head[u]};

	head[u]=cnt;

}

int n,a[N],dfn[N],tim=0,tmp[N];

priority_queue <int> q[N];

ll ans=0;

inline void dfs(register int x)

{

	dfn[x]=++tim;

	for(register int i=head[x];i;i=e[i].next)

	{

		int v=e[i].to;

		if(dfn[v])

			continue;

		dfs(v);

		if(q[dfn[x]].size()<q[dfn[v]].size())

			dfn[x]^=dfn[v]^=dfn[x]^=dfn[v];

		int m=q[dfn[v]].size();

		for(register int i=1;i<=m;++i)

		{

			tmp[i]=Max(q[dfn[x]].top(),q[dfn[v]].top());

			q[dfn[x]].pop(),q[dfn[v]].pop();

		}

		for(register int i=1;i<=m;++i)

			q[dfn[x]].push(tmp[i]);

	}

	q[dfn[x]].push(a[x]);

}

int main()

{

	n=read();

	for(register int i=1;i<=n;++i)

		a[i]=read();

	for(register int i=2;i<=n;++i)

	{

		int fa=read();

		add(fa,i),add(i,fa);

	}

	dfs(1);

	while(!q[dfn[1]].empty())

	{

		ans+=1ll*q[dfn[1]].top();

		q[dfn[1]].pop();

	}

	write(ans);

	return 0;

}

巴特西

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

原题传送门

每个点维护一个堆，表示这个点及其子树所需的每段内存的空间

搜索时从下向上做启发式合并堆中信息，最后根节点堆中所有内存空间之和就是答案

最新文章

热门文章