分数: 500 点
问题陈述
你得到了一棵树 N 顶点。 对于每个 i = 1, 2, \ldots, N-1, i第一条边连接顶点 u_i 和顶点 v_i 并且有一个重量 w_i.
考虑选择一些 N-1 边缘(可能没有或全部)。 在这里,对于每一个 i = 1, 2, \ldots, N,最多可以选择一个 d_i 入射到顶点的边 i。 找出所选边的最大可能总权重。
约束
- 2 \leq N \leq 3 \times 10^5
- 1 \leq u_i, v_i \leq N
- -10^9 \leq w_i \leq 10^9
- d_i 是一个不超过 Vertex 度数的非负整数 i.
- 给定的图是一棵树。
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N
d_1 d_2 \ldots d_N
u_1 v_1 w_1
u_2 v_2 w_2
\vdots
u_{N-1} v_{N-1} w_{N-1}
输出
打印答案。
示例输入 1
7 1 2 1 0 2 1 1 1 2 8 2 3 9 2 4 10 2 5 -3 5 6 8 5 7 3
示例输出 1
28
如果您选择 1-st, 2-nd, 5-th,以及 6第条边,这些边的总权重为 8 + 9 + 8 + 3 = 28。这是最大可能的值。
示例输入 2
20 0 2 0 1 2 1 0 0 3 0 1 1 1 1 0 0 3 0 1 2 4 9 583 4 6 -431 5 9 325 17 6 131 17 2 -520 2 16 696 5 7 662 17 15 845 7 8 307 13 7 849 9 19 242 20 6 909 7 11 -775 17 18 557 14 20 95 18 10 646 4 3 -168 1 3 -917 11 12 30
示例输出 2
2184