BZOJ3252: 攻略 可并堆

网上有很多人说用dfs序+线段树做...其实stl的堆可以...可并堆可以...很多奇奇怪怪的东西都能做...

可并堆比较好想...也比较好写...

分析：

首先，这是一个网络流做不了的题...数据太大...

其次...我们可以这样考虑一下，这个点的子树中，将这个点的权值仅更新给最大的那个就能满足

之后，在每一个叶子节点上，建立一个大根堆，dfs一遍，将子节点的堆合并，之后找到根节点，将根节点的权值加上当前位置的价值

最后，根节点中前k大的权值和即为答案...

附上代码，精简可行

#include <cstdio>

#include <algorithm>

#include <queue>

#include <iostream>

#include <cstdlib>

#include <cmath>

#include <cstring>

using namespace std;

#define N 200005

#define ll long long

struct node

{

	int ls,rs,dis;

	ll x;

}mp[N<<1];

struct no

{

	int to,next;

}e[N<<1];

int head[N],cnt,fa[N],a[N],n,K;

void add(int x,int y)

{

	e[cnt].to=y;

	e[cnt].next=head[x];

	head[x]=cnt++;

	return ;

}

int merge(int x,int y)

{

	if(!x)return y;

	if(!y)return x;

	if(mp[x].x<mp[y].x)swap(x,y);

	mp[x].rs=merge(mp[x].rs,y);

	if(mp[mp[x].rs].dis>mp[mp[x].ls].dis)swap(mp[x].ls,mp[x].rs);

	mp[x].dis=mp[mp[x].rs].dis+1;

	return x;

}

void dfs(int x,int from)

{

	for(int i=head[x];i!=-1;i=e[i].next)

	{

		int to1=e[i].to;

		if(to1!=from)

		{

			dfs(to1,x);

			fa[x]=merge(fa[to1],fa[x]);

		}

	}

	mp[fa[x]].x+=a[x];

}

int in1[N];

int main()

{

	memset(head,-1,sizeof(head));

	scanf("%d%d",&n,&K);

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

	{

		scanf("%d",&a[i]);

	}

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

	{

		int x,y;

		scanf("%d%d",&x,&y);

		in1[x]++,in1[y]++;

		add(x,y);

		add(y,x);

	}

	int rot=1,num=0;

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

	{

		if(in1[1]==1&&in1[i]!=1)

		{

			rot=i;

		}else

		{

			num++;

			fa[i]=i;

		}

	}

	K=min(num,K);

	dfs(rot,0);

	ll ans=0;

	while(K--)

	{

		ans+=mp[fa[rot]].x;

		mp[fa[rot]].x=0;

		fa[rot]=merge(mp[fa[rot]].ls,mp[fa[rot]].rs);

	}

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

	return 0;

}