bzoj 4585: [Apio2016]烟火表演【左偏树】

参考：https://blog.csdn.net/wxh010910/article/details/55806735

以下课件，可并堆部分写的左偏树

#include<iostream>

#include<cstdio>

using namespace std;

const int N=600005;

int n,m,tot,fa[N],len[N],rt[N],d[N],cnt;

long long p[N],sum;

int read()

{

	int r=0,f=1;

	char p=getchar();

	while(p>'9'||p<'0')

	{

		if(p=='-')

			f=-1;

		p=getchar();

	}

	while(p>='0'&&p<='9')

	{

		r=r*10+p-48;

		p=getchar();

	}

	return r*f;

}

struct qwe

{

	int l,r,dis;

	long long v;

}e[N];

int hb(int x,int y)

{

	if(!x||!y)

		return x+y;

	if(e[x].v<e[y].v)

		swap(x,y);

	e[x].r=hb(e[x].r,y);

	if(e[e[x].l].dis<e[e[x].r].dis)

		swap(e[x].l,e[x].r);

	if(!e[x].r)

		e[x].dis=0;

	else

		e[x].dis=e[e[x].r].dis+1;

	return x;

}

int pop(int x)

{

	return hb(e[x].l,e[x].r);

}

int main()

{

	n=read(),m=read();

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

	{

		fa[i]=read(),len[i]=read();

		sum+=len[i];

		d[fa[i]]++;

	}

	for(int i=m+n;i>1;i--)

	{

		long long l=0,r=0;

		if(i<=n)

		{

			while(--d[i])

				rt[i]=pop(rt[i]);

			r=e[rt[i]].v;

			rt[i]=pop(rt[i]);

			l=e[rt[i]].v;

			rt[i]=pop(rt[i]);

		}

		e[++tot].v=l+len[i];

		e[++tot].v=r+len[i];

		rt[i]=hb(rt[i],hb(tot,tot-1));

		rt[fa[i]]=hb(rt[fa[i]],rt[i]);

	}

	while(d[1]--)

		rt[1]=pop(rt[1]);

	while(rt[1])

		p[++cnt]=e[rt[1]].v,rt[1]=pop(rt[1]);

	for(int i=1;i<=cnt;i++)

		sum-=p[i];

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

	return 0;

}

巴特西

bzoj 4585: [Apio2016]烟火表演【左偏树】

最新文章

热门文章