Select Edges

题目描述

给定一个有 $N$ 个顶点的树。 对于每个 $i = 1, 2, \ldots, N-1$，第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$，权重为 $w_i$。 考虑从这 $N-1$ 条边中选择若干条（可以不选或全部选择）。 在这里，对于每个 $i = 1, 2, \ldots, N$，至多可选择与顶点 $i$ 相邻的 $d_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}$

输出格式

输出答案。

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

28

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

2184

提示

$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$ 是不超过顶点 $i$ 的度的非负整数。 给定的图是树。 输入中的所有数值都是整数。如果你选择第 $1$ 条、第 $2$ 条、第 $5$ 条和第 $6$ 条边，这些边的权重总和为 $8 + 9 + 8 + 3 = 28$。这是可能的最大值。

标签: AtCoder|abc259F

来源

AtCoder|abc259F