攻略

时间限制:10s      空间限制:128MB

题目描述

题目简述:树版[k取方格数]
 
众所周知,桂木桂马是攻略之神,开启攻略之神模式后,他可以同时攻略k部游戏。
今天他得到了一款新游戏《XX半岛》,这款游戏有n个场景(scene),某些场景可以通过不同的选择支到达其他场景。所有场景和选择支构成树状结构:开始游戏时在根节点(共通线),叶子节点为结局。每个场景有一个价值,现在桂马开启攻略之神模式,同时攻略k次该游戏,问他观赏到的场景的价值和最大是多少(同一场景观看多次是不能重复得到价值的)
“为什么你还没玩就知道每个场景的价值呢?”
“我已经看到结局了。”


输入格式

第一行两个正整数n,k
第二行n个正整数,表示每个场景的价值
以下n-1行,每行2个整数a,b,表示a场景有个选择支通向b场景(即a是b的父亲)
保证场景1为根节点


输出格式

 
输出一个整数表示答案


样例输入

5 2
4 3 2 1 1
1 2
1 5
2 3
2 4

样例输出

10

提示

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


题目来源

dfs序+线段树

Menuappsclose