← 返回题目列表

AtCoder · abc259_f

I. 选择边缘

中文机器翻译题面 查看原题

分数: 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