Bzoj3252 攻略

Posted by yjjr's blog on February 6, 2018

标签:贪心,dfs

Description

题目简述:树版[k取方格数]

 

众所周知,桂木桂马是攻略之神,开启攻略之神模式后,他可以同时攻略k部游戏。

今天他得到了一款新游戏《XX半岛》,这款游戏有n个场景(scene),某些场景可以通过不同的选择支到达其他场景。所有场景和选择支构成树状结构:开始游戏时在根节点(共通线),叶子节点为结局。每个场景有一个价值,现在桂马开启攻略之神模式,同时攻略k次该游戏,问他观赏到的场景的价值和最大是多少(同一场景观看多次是不能重复得到价值的)

“为什么你还没玩就知道每个场景的价值呢?”

“我已经看到结局了。”

Input

第一行两个正整数n,k

第二行n个正整数,表示每个场景的价值

以下n-1行,每行2个整数a,b,表示a场景有个选择支通向b场景(即a是b的父亲)

保证场景1为根节点

Output

 

输出一个整数表示答案

Sample Input

5 2

4 3 2 1 1

1 2

1 5

2 3

2 4

Sample Output

10

HINT

对于100%的数据,n<=200000,1<=场景价值<=2^31-1

Source

dfs序+线段树

 

分析:这题是钟长者出的模拟题,但因为不明原因搞上了bzoj

很多人都是线段树+dfs序的做法

实际上并不需要

可以先dfs一遍,处理出w[x]表示以x为根节点的子树中取一条价值和最大的链

每次选择x中w[son]最大的一个转移:w[x]=max(w[son])+a[x]

然后将w排序,转化为c数组,取前k大

 

Code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#define rep(i,a,b) for(register int i=a;i<=b;i++)
#define dep(i,a,b) for(register int i=a;i>=b;i--)
#define mem(x,num) memset(x,num,sizeof x)
#define v e[i].to
#define ll long long
#ifdef WIN32
#define LL "%I64d"
#else 
#define LL "%lld"
#endif
using namespace std;
inline ll read()
{
    ll f=1,x=0;char ch=getchar(); 
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
const  ll maxn=2e5+6;
ll head[maxn],a[maxn],n,k,w[maxn],cnt=0,c[maxn],tot=0;
struct edge{ll to,next;}e[maxn<<1];
#define v e[i].to
#define reg(x) for(int i=head[x];i;i=e[i].next)
inline bool cmp(ll x,ll y){return x>y;}
void dfs(int x,int fa)
{
    ll Max=0,mx;
	reg(x)
	{
		if(v==fa)continue;
		dfs(v,x);
		if(w[v]>Max)Max=w[v],mx=v;
	}
	w[x]=Max+a[x];
	reg(x)
	{
		if(v==fa||v==mx)continue;
		c[++tot]=w[v];
	}
}
		
int main()
{
	n=read(),k=read();
	rep(i,1,n)a[i]=read();
	rep(i,1,n-1){
		int U=read(),V=read();
		e[++cnt]=(edge){V,head[U]};head[U]=cnt;
		e[++cnt]=(edge){U,head[V]};head[V]=cnt;
	}
	tot=0;dfs(1,1);
	c[++tot]=w[1];
	sort(c+1,c+1+tot,cmp);
	ll ans=0;
	k=min(k,tot);
	rep(i,1,k)ans+=c[i];
	cout<<ans<<endl;
	return 0;
}



本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr