分数: 425 点
问题陈述
你得到了一棵树 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 正电子放置在顶点 i。如果 x_i < 0,那么 -x_i 电子放置在顶点 i。如果 x_i=0,则顶点处不放置任何内容 i。在此,可以保证 \sum_{i=1}^N x_i = 0.
沿边缘移动一个正电子或电子 j 消耗能源 w_j。此外,当正电子和电子位于同一顶点时,它们会以相同数量相互湮灭。
求湮灭所有正电子和电子所需的最小能量。
约束
- 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
- 给定的图是一棵树。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
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}
输出
输出答案。
示例输入 1
4 -3 2 2 -1 1 2 2 1 3 1 1 4 3
示例输出 1
9
最初, x=(x_1,x_2,x_3,x_4)=(-3,+2,+2,-1)。 通过如下操作,所有正电子和电子都可以被能量湮灭 9:
- 在顶点移动一个电子 1 到顶点 2。这需要消耗能量 2,和 x=(-2,+1,+2,-1).
- 在顶点移动一个正电子 2 到顶点 1。这需要消耗能量 2,和 x=(-1,0,+2,-1).
- 在顶点移动一个电子 4 到顶点 1。这需要消耗能量 3,和 x=(-2,0,+2,0).
- 在顶点移动一个电子 1 到顶点 3。这需要消耗能量 1,和 x=(-1,0,+1,0).
- 在顶点移动一个电子 1 到顶点 3。这需要消耗能量 1,和 x=(0,0,0,0).
不可能用能量湮灭所有正电子和电子 8 或更少,所以答案是 9.
示例输入 2
2 0 0 1 2 1
示例输出 2
0
条件可能从一开始就已经满足。
示例输入 3
5 -2 -8 10 -2 2 3 5 1 1 3 5 2 5 0 3 4 6
示例输出 3
28