AT_abc409_e [ABC409E] Pair Annihilation

[problemUrl]: https://atcoder.jp/contests/abc409/tasks/abc409_e 给定一棵包含 $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 完成