【刷题】BZOJ 3252 攻略

Description

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

众所周知,桂木桂马是攻略之神,开启攻略之神模式后,他可以同时攻略k部游戏。今天他得到了一款新游戏《XX

半岛》,这款游戏有n个场景(scene),某些场景可以通过不同的选择支到达其他场景。所有场景和选择支构成树状

结构:开始游戏时在根节点(共通线),叶子节点为结局。每个场景有一个价值,现在桂马开启攻略之神模式,同

时攻略k次该游戏,问他观赏到的场景的价值和最大是多少(同一场景观看多次是不能重复得到价值的)

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

“我已经看到结局了。”

Input

第一行两个正整数n,k

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

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

保证场景1为根节点

n<=200000,1<=场景价值<=2^31-1

Output

输出一个整数表示答案

Sample Input

5 2

4 3 2 1 1

1 2

1 5

2 3

2 4

Sample Output

10

Solution

考虑贪心,我们需要找满足以下条件的 \(k\) 条路径:

路径与路径之间没有重叠(以不重复计算贡献);每条路径的终点一定是叶子;每条路径要可以直接或间接地到达根(即通过其它路径)

然后答案要最大,那么就是要找权值和最大的 \(k\) 条路径

会发现,这些东西极其地类似于长链剖分。我们如果按照权值进行长链剖分,可以最优地将树分割成满足条件的一个个路径,取最大的 \(k\) 个即可

大概证明一下,首先长链剖分,每条链都是到达叶子节点的,并且肯定不会重复;然后因为是按照权值来剖分的,所以如果最终我们选了一个起点不是根的链,那么它的的起点的父亲所在的链一定被选了,因为它们是重链和轻链的关系

#include<bits/stdc++.h>
#define ui unsigned int
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
#define REP(a,b,c) for(register int a=b,a##end=c;a<=a##end;++a)
#define DEP(a,b,c) for(register int a=b,a##end=c;a>=a##end;--a)
const int MAXN=200000+10;
int n,k,e,beg[MAXN],nex[MAXN],to[MAXN],val[MAXN],top[MAXN],hson[MAXN];
ll sum[MAXN],Mx[MAXN],ans;
std::priority_queue<ll> q;
template<typename T> inline void read(T &x)
{
T data=0,w=1;
char ch=0;
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')w=-1,ch=getchar();
while(ch>='0'&&ch<='9')data=((T)data<<3)+((T)data<<1)+(ch^'0'),ch=getchar();
x=data*w;
}
template<typename T> inline void write(T x,char ch='\0')
{
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+'0');
if(ch!='\0')putchar(ch);
}
template<typename T> inline void chkmin(T &x,T y){x=(y<x?y:x);}
template<typename T> inline void chkmax(T &x,T y){x=(y>x?y:x);}
template<typename T> inline T min(T x,T y){return x<y?x:y;}
template<typename T> inline T max(T x,T y){return x>y?x:y;}
inline void insert(int x,int y)
{
to[++e]=y;
nex[e]=beg[x];
beg[x]=e;
}
inline void dfs1(int x,int f)
{
hson[x]=x;sum[x]=sum[f]+val[x];
for(register int i=beg[x];i;i=nex[i])
{
dfs1(to[i],x);
if(Mx[to[i]]>Mx[x])Mx[x]=Mx[to[i]],hson[x]=to[i];
}
Mx[x]+=val[x];
}
inline void dfs2(int x,int tp)
{
top[x]=tp;
if(hson[x]!=x)dfs2(hson[x],tp);
for(register int i=beg[x];i;i=nex[i])
if(to[i]==hson[x])continue;
else dfs2(to[i],to[i]);
}
inline void dfs(int x)
{
int ch=0;
for(register int i=beg[x];i;i=nex[i])dfs(to[i]),ch++;
if(!ch)q.push(sum[x]-sum[top[x]]+val[top[x]]);
}
int main()
{
read(n);read(k);
REP(i,1,n)read(val[i]);
REP(i,1,n-1)
{
int u,v;read(u);read(v);
insert(u,v);
}
dfs1(1,0);dfs2(1,1);dfs(1);
while(!q.empty()&&k--)ans+=q.top(),q.pop();
write(ans,'\n');
return 0;
}
上一篇:英语词汇语法-系列-[0001]


下一篇:[HYSBZ - 3252] 攻略