AT_abc409_e.[ABC409E] Pair Annihilation

给定一棵包含 $N$ 个顶点的树。顶点编号为 $1,2,\dots,N$，边编号为 $1,2,\dots,N-1$。边 $j$ 双向连接顶点 $u_j$ 和 $v_j$，其权重为 $w_j$。此外，顶点 $i$ 上有一个整数 $x_i$：若 $x_i > 0$，表示该顶点有 $x_i$ 个正电子；若 $x_i < 0$，表示有 $-x_i$ 个电子；若 $x_i = 0$，则该顶点没有粒子。题目保证 $\sum_{i=1}^N x_i = 0$。

每次可以沿边 $j$ 移动 1 个正电子或电子，消耗能量 $w_j$。当正电子和电子位于同一顶点时，它们会相互抵消（数量相等时完全消失）。

求使所有正电子和电子完全消失所需的最小总能量。

输入通过标准输入给出，格式如下：

$N$
$x_1$ $x_2$ $\dots$ $x_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 10^5$
• $|x_i| \leq 10^4$
• $\sum_{i=1}^N x_i = 0$
• $1 \leq u_j < v_j \leq N$
• $0 \leq w_j \leq 10^4$
• 给定的图是一棵树
• 输入均为整数

样例解释 1

初始状态 $x=(-3,+2,+2,-1)$。通过以下操作可以用最小能量 $9$ 使所有粒子消失：

1. 将顶点 $1$ 的 1 个电子移动到顶点 $2$，消耗能量 $2$，$x=(-2,+1,+2,-1)$；
2. 将顶点 $2$ 的 1 个正电子移动到顶点 $1$，消耗能量 $2$，$x=(-1,0,+2,-1)$；
3. 将顶点 $4$ 的 1 个电子移动到顶点 $1$，消耗能量 $3$，$x=(-2,0,+2,0)$；
4. 将顶点 $1$ 的 1 个电子移动到顶点 $3$，消耗能量 $1$，$x=(-1,0,+1,0)$；
5. 将顶点 $1$ 的 1 个电子移动到顶点 $3$，消耗能量 $1$，$x=(0,0,0,0)$。

无法用 $8$ 或更少能量完成目标，因此答案为 $9$。

样例解释 2

初始状态已满足条件时，输出 $0$。

翻译由 DeepSeek V3 完成