#P3252. 攻略
攻略
攻略
题目描述
桂木桂马得到了一款游戏《XX 半岛》。游戏的 个场景由剧情选项连成一棵有根树。每次从根场景开始,沿剧情选项一直走到某个叶子场景,即一个结局。
桂马同时攻略 次,每次可以自行选择路线。每个场景有一个价值,多次经过同一个场景只计一次价值。求能获得的总价值的最大值。
“为什么你还没玩就知道每个场景的价值呢?”
“我已经看到结局了。”
输入格式
第一行包含两个正整数 。第二行包含 个正整数,按编号给出各场景的价值。
接下来 行,每行两个整数 ,表示从场景 有一个剧情选项通向场景 。场景 是根。
输出格式
输出一个整数,表示能获得的最大总价值。
样例
5 2
4 3 2 1 1
1 2
1 5
2 3
2 4
10
数据规模与约定
,每个场景的价值在 内。