luogu#P3925. aaa被续
aaa被续
题目背景
HansBug持续无聊ing
题目描述
由于aaa没有完成HansBug的任务。所以HansBug开始计划着如何续aaa。
现在HansBug手里有 个aaa,每个aaa有一个码力值。一共存在 条连接两个aaa的边,故这 个aaa构成一棵有根树,根为1号aaa。
现在HansBug想要续了这 个aaa。HansBug所采用的策略是,对于第 个aaa,先让他和他的各级子aaa们乖乖♂站好成一队,然后依次续掉。
经过长期对于aaa码力值的研究,HansBug发现,对于每一队aaa,设有 个,码力值依次为,则续了队伍里的第 个aaa所能获得的码力值为 。
然而,aaa之间的关系树相当的复杂,HansBug的智商早已不够用,于是这个任务就交给了你。不过HansBug知道,任何一个aaa都不会有超过5个的直接子aaa
HansBug想要知道在每次排♂队方法最优的情况下,续了这些aaa最多可以获得的码力值~~,事成之后分给你100000 % 10点码力值~~。
输入格式
第一行包含一个正整数 ,表示aaa的个数。
接下来 行,每行包含两个正整数 ,代表第 个aaa和第 个aaa之间存在从属关系(最高级别的aaa编号为 )
最后一行包含 个非负整数,依次代表第 个aaa的码力值。
输出格式
输出包含一个整数,打表HansBug续掉全部的aaa之后最多能获得的码力值。
由于结果较大,所以请对 取模 ()
5
5 3
1 2
1 5
4 5
3 9 10 4 7
189
提示
样例解释:
故续了5个aaa所得的最大总码力值为:118 + 9 + 10 + 4 + 48 = 189
对1000000007取模后得到答案189
数据范围:
对于30%的数据:
对于50%的数据:
对于70%的数据:
对于100%的数据:
对于每一个aaa的码力值 ,保证