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

这题是最近看到的今年省选题中最良心的一道了吧

看题+想题+写题都可以在0.5h内解决，送分含义明显啊

首先理解了题意后我们很快就能发现两个点如果要被分在一段那么必须在它们的祖先处合并

首先我们考虑下二叉树怎么做，发现如果对于每个节点维护一个堆，然后每次在一个点合并两个儿子的堆

根据简单分析我们发现必然是不断取出两个堆中最大的元素合并直到一个空了为止

那么普通的树怎么做呢，如果你稍微有点经验就会发现这个很好扩展，直接把所有儿子合并即可

但是这样一个元素可能会重复入堆多次，解决方法也很简单，直接启发式合并即可

值得一提的是这里的启发式合并由于再合并后短的相当于被直接扔掉了，因此每个元素合并\(n\)次，总复杂度是\(n\log n\)的

CODE

#include<cstdio>

#include<cctype>

#include<queue>

#define RI register int

#define CI const int&

#define Tp template <typename T>

using namespace std;

const int N=200005;

struct edge

{

	int to,nxt;

}e[N]; int n,x,head[N],cnt,a[N],id[N],t[N]; priority_queue <int> hp[N]; long long ans;

class FileInputOutput

{

	private:

		static const int S=1<<21;

		#define tc() (A==B&&(B=(A=Fin)+fread(Fin,1,S,stdin),A==B)?EOF:*A++)

		char Fin[S],*A,*B;

	public:

		Tp inline void read(T& x)

		{

			x=0; char ch; while (!isdigit(ch=tc()));

			while (x=(x<<3)+(x<<1)+(ch&15),isdigit(ch=tc()));

		}

		#undef tc

}F;

inline void addedge(CI x,CI y)

{

	e[++cnt]=(edge){y,head[x]}; head[x]=cnt;

}

inline void swap(int& x,int& y)

{

	int t=x; x=y; y=t;

}

inline int max(CI x,CI y)

{

	return x>y?x:y;

}

#define to e[i].to

inline void DFS(CI now)

{

	id[now]=now; for (RI i=head[now];i;i=e[i].nxt)

	{

		DFS(to); if (hp[id[now]].size()<hp[id[to]].size()) swap(id[now],id[to]);

		RI cnt=0; while (!hp[id[to]].empty()) t[++cnt]=max(hp[id[now]].top(),hp[id[to]].top()),

		hp[id[now]].pop(),hp[id[to]].pop(); while (cnt) hp[id[now]].push(t[cnt--]);

	}

	hp[id[now]].push(a[now]);

}

#undef to

int main()

{

	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);

	RI i; for (F.read(n),i=1;i<=n;++i) F.read(a[i]);

	for (i=2;i<=n;++i) F.read(x),addedge(x,i); DFS(1);

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

	return printf("%lld",ans),0;

}

巴特西

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

最新文章

热门文章