「BZOJ3252」攻略

2014年11月25日5,9461

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

题解

首先显然每次取最大权和的链

bzoj上标签贴的是dfs序+线段树。。。

每次从底端选个最大权和点,将它到根的链取走,对于链上的每个点x,要将x子树内的叶节点的权值和减去x的权值,因为下次取x子树的叶节点不能再次得到x的权值,用dfs+线段树就可以实现每次找叶节点最大值,以及修改子树权值

我写的是另一种做法

发现每次一定是选取一个点,将它子树内权值和最大的链取走,以后就不会再选取链上的点

那么用堆维护这一过程,取最大值,删去链的所有点

复杂度都为nlogn

 

avatar
1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
0 Comment authors
Recent comment authors
  Subscribe  
提醒
trackback

[…] Orz hzwer […]