luogu#P3925. aaa被续

    ID: 7953 远端评测题 1500ms 125~250MiB 尝试: 0 已通过: 0 难度: 6 上传者: 标签>线段树树状数组洛谷原创O2优化树链剖分树剖洛谷月赛

aaa被续

题目背景

HansBug持续无聊ing

题目描述

由于aaa没有完成HansBug的任务。所以HansBug开始计划着如何续aaa。

现在HansBug手里有 N N 个aaa,每个aaa有一个码力值。一共存在 N1 N - 1 条连接两个aaa的边,故这 N N 个aaa构成一棵有根树,根为1号aaa。

现在HansBug想要续了这 N N 个aaa。HansBug所采用的策略是,对于第 i i个aaa,先让他和他的各级子aaa们乖乖♂站好成一队,然后依次续掉。

经过长期对于aaa码力值的研究,HansBug发现,对于每一队aaa,设有 nn个,码力值依次为vi v_i ,则续了队伍里的第 i i 个aaa所能获得的码力值为 v1+v2++vi v_1 + v_2 + \cdots + v_i

然而,aaa之间的关系树相当的复杂,HansBug的智商早已不够用,于是这个任务就交给了你。不过HansBug知道,任何一个aaa都不会有超过5个的直接子aaa

HansBug想要知道在每次排♂队方法最优的情况下,续了这些aaa最多可以获得的码力值~~,事成之后分给你100000 % 10点码力值~~。

输入格式

第一行包含一个正整数 N N ,表示aaa的个数。

接下来 N1 N-1 行,每行包含两个正整数 u,v u, v,代表第 uu 个aaa和第 v v 个aaa之间存在从属关系(最高级别的aaa编号为 1 1

最后一行包含 N N 个非负整数,依次代表第 i i 个aaa的码力值。

输出格式

输出包含一个整数,打表HansBug续掉全部的aaa之后最多能获得的码力值。

由于结果较大,所以请对 1000000007 1000000007 取模 (109+7 {10} ^ 9 + 7

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%的数据:1N3103 1 \leq N \leq 3 \cdot {10}^3

对于50%的数据:1N2104 1 \leq N \leq 2 \cdot {10}^4

对于70%的数据:1N105 1 \leq N \leq {10}^5

对于100%的数据:1N5105 1 \leq N \leq 5 \cdot {10}^5

对于每一个aaa的码力值 ai a_i ,保证 0ai108 0 \leq a_i \leq {10}^8