选择矿洞

题目内容

题目描述

在A城有一个矿区,矿区内有n(n<=2 × 105)个矿洞,编号为1到n,在第i个矿洞进行开采可以获得的收益为 vi(0 <= vi<= 1000)。矿洞之间有n-1条道路相连,且任意两个矿洞之间有且只有一条路径。出于安全考虑,要求每条道路两端的矿洞最多只能选择其中一个进行开采。求一种选择矿洞的方案,使得获得的收益总和最大。

输入描述

输入的第一行为一个正整数n,代表矿洞的个数。

接下来n-1行,每行两个正整数x和y,代表第x个矿洞和第y个矿洞之间有一条道路。

最后一行为n个整数,用空格隔开,第i个整数代表在第i个矿洞开采可以获得的收益vi

输出描述

输出一个正整数,代表可以获得的最大收益。

样例输入

5 1 2 2 3 2 4 4 5 10 20 20 40 60

样例输出

90

提示

提交评测
请登录后再操作

题目描述

选择矿洞
1158
0
Level3
64
38
59%
证书查询 x
请输入证书编号:

请输入正确的证书编号

学员姓名:孙兴民

课程:Scratch Level 1

发证日期:2019.08.15

证书查询

该证书不存在