← 返回题目列表

AtCoder · abc409_e

H. 配对歼灭

中文机器翻译题面 查看原题

分数: 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