AT_abc259_f [ABC259F] Select Edges

给定一棵有 $N$ 个顶点的树。对于 $i=1,2,\ldots,N-1$，第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$，其权值为 $w_i$。 你可以从 $N-1$ 条边中选择若干条（可以选择 $0$ 条，也可以选择全部 $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}$

输出一个整数，表示最大可能的边权和。

## 限制条件 - $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 选择第 $1,2,5,6$ 条边时，所选边的权值之和为 $8+9+8+3=28$，这是可能得到的最大值。 由 ChatGPT 4.1 翻译