3696: 牛牛的旅行(第五轮02)
题目描述
国庆长假， 牛牛准备去旅游。牛牛所在的景区有N个景点， 景点和景点之间一共 有N − 1条线路相连，同时，每个景点还有一个优美程度vali 。
对于树上的一条游览路线，牛牛用它的两个端点s, t来表示，牛牛以s为起点，t为 终点。在树上沿最短路线移动。
我们定义happy(s, t)为牛牛在一条游览路线游玩时获得的快乐度。
牛牛每移动一条道路，他的快乐度就会下降 1， 牛牛将选择这条游览路线中优美 程度最大的景点观赏，这将使得他的快乐度上升valmax ，其中valmax 表示游览路 线中优美程度最大景点的优美程度。
现在牛牛想要知道给定景点的树结构，以及优美程度的情况下，对于所有端点s ≠ t时的happy(s, t)之和是多少。
具体来讲， 你要求出Σs≠t happy(s, t)的值，由于这个数字很大，请输出结果对 109 + 7取模后的结果。
对于连接景点树结构上的一条边，在输入时用点对(u, v)表示景点树结构中节点u 和节点v是直接相连的。
当然了， 由于本题的最终答案有可能是一个负数，为了避免这个问题，要求你要 输出一个模系负数， 即你需要保证最终结果在[0,109 + 7)的范围内，如果答案小
于 0，则需要对109 + 7取余数后再加上109 + 7，例子见样例三。
输入
第一行输入一个正整数N，表示景点的数目。
接下来一行输入N个非负整数vali，表示每个景点的优美程度。
接下来N − 1行，每行两个正整数u, v，表示景区树结构上的一条边。
输出
仅一行，表示Σs≠t happy(s, t)对109 + 7取模的结果。。
样例输入 复制
4
1 5 1 1
1 2
2 3
2 4样例输出 复制
42提示
【样例 1 输入】
4
1 5 1 1
1 2
2 3
2 4
【样例 1 输出】
42
【样例 2 输入】
2
1 1
1 2
【样例 2 输出】
0
【样例 3 输入】
3
0 0 0
1 2
2 3
【样例 3 输出】
999999999
【样例 3 说明】
最终的答案为−8， 在对109 + 7取模的情况下， −8 ≡ 999999999，所以要输出 999999999。
【样例 4 输入】
103
46126090 175339731 182218866 886687896 730875993 24459890 875266727
296787757 629407288 562696485 882250206 797791334 39423402 48988690
581165415 968426243 741608552 692362674 736017028 982653783 886420062
217335890 672364778 147280842 753126956 743035540 881846083 16621398
52824487 616980972 392489903 756592650 734395990 341715235 715424830
896332682 260938229 45609176 262345592 34350989 53170933 308965370
708279509 637495390 107916538 977269839 603492677 941673307 193465692
108255984 931285930 945684345 105635751 569628874 61889881 22672318
57543195 664834846 652249757 666241477 130495020 998967298 573822771
591807038 932204802 741885663 80478927 676856172 94640122 467433713
521000342 183750053 717235492 832584138 38040225 263297493 616859588
316522447 770258561 150738427 39242449 610292921 114626485 11929002
472550264 329621013 49653045 259924617 406161818 673035716 76034795
38416084 486133834 476746364 619551797 364370905 247486544 67434053
871550053 27331196 980661929 511928574 17502529
1 2
2 3
2 4
3 5
2 6
6 7
6 8
1 9
1 10
10 11
9 12
2 13
2 14
6 15
5 16
15 17
13 18
3 19
1 20
3 21
13 22
9 23
22 24
12 25
3 26
15 27
16 28
24 29
3 30
29 31
24 32
25 33
7 34
2 35
25 36
5 37
23 38
35 39
24 40
31 41
12 42
5 43
11 44
4 45
28 46
26 47
34 48
38 49
5 50
3 51
16 52
1 53
43 54
18 55
2 56
41 57
16 58
6 59
16 60
25 61
58 62
54 63
6 64
63 65
22 66
2 67
62 68
53 69
30 70
12 71
33 72
42 73
34 74
2 75
4 76
75 77
67 78
30 79
65 80
43 81
25 82
44 83
7 84
67 85
16 86
84 87
86 88
50 89
59 90
31 91
75 92
7 93
18 94
10 95
21 96
82 97
62 98
74 99
26 100
54 101
31 102
22 103
【样例 4 输出】
682124261
【数据范围】
由于本题的输入量很大，请注意，请勿使用 c++的 cin 读入导致超时。
请使用 scanf 函数，或者其他更快的读入方式。
对于前 30%的测试数据，保证N ≤ 1000。
对于另 10%的测试数据，保证景区构成的树结构退化为一条单链。
对于另 10%的测试数据，保证所有景点的优美程度vali 都相同。
对于 100%的测试数据，保证2 ≤ N ≤ 10^6, 1 ≤ u, v ≤ N, 0 ≤ vqli < 10^9 + 7。