H - Pair Annihilation Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 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 個の陽電子が、x_i < 0 なら -x_i 個の電子が頂点 i に置かれています。x_i=0 ならば頂点 i には何もありません。ここで、\sum_{i=1}^N x_i = 0 が保証されます。

陽電子または電子 1 個を辺 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 にある電子を 1 つ、頂点 2 に移動させる。エネルギー 2 がかかり、x=(-2,+1,+2,-1) となる。
  • 頂点 2 にある陽電子を 1 つ、頂点 1 に移動させる。エネルギー 2 がかかり、x=(-1,0,+2,-1) となる。
  • 頂点 4 にある電子を 1 つ、頂点 1 に移動させる。エネルギー 3 がかかり、x=(-2,0,+2,0) となる。
  • 頂点 1 にある電子を 1 つ、頂点 3 に移動させる。エネルギー 1 がかかり、x=(-1,0,+1,0) となる。
  • 頂点 1 にある電子を 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

Score : 425 points

Problem Statement

You are given a tree with N vertices. The vertices are numbered 1,2,\dots,N, and the edges are numbered 1,2,\dots,N-1. Edge j bidirectionally connects vertices u_j and v_j and has weight w_j. Also, vertex i is given an integer x_i. If x_i > 0, then x_i positrons are placed at vertex i. If x_i < 0, then -x_i electrons are placed at vertex i. If x_i=0, then nothing is placed at vertex i. Here, it is guaranteed that \sum_{i=1}^N x_i = 0.

Moving one positron or electron along edge j costs energy w_j. Also, when a positron and an electron are at the same vertex, they annihilate each other in equal numbers.

Find the minimum energy required to annihilate all positrons and electrons.

Constraints

  • 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
  • The given graph is a tree.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

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}

Output

Output the answer.

Sample Input 1

4
-3 2 2 -1
1 2 2
1 3 1
1 4 3

Sample Output 1

9

Initially, x=(x_1,x_2,x_3,x_4)=(-3,+2,+2,-1). By operating as follows, all positrons and electrons can be annihilated with energy 9:

  • Move one electron at vertex 1 to vertex 2. This costs energy 2, and x=(-2,+1,+2,-1).
  • Move one positron at vertex 2 to vertex 1. This costs energy 2, and x=(-1,0,+2,-1).
  • Move one electron at vertex 4 to vertex 1. This costs energy 3, and x=(-2,0,+2,0).
  • Move one electron at vertex 1 to vertex 3. This costs energy 1, and x=(-1,0,+1,0).
  • Move one electron at vertex 1 to vertex 3. This costs energy 1, and x=(0,0,0,0).

It is impossible to annihilate all positrons and electrons with energy 8 or less, so the answer is 9.

Sample Input 2

2
0 0
1 2 1

Sample Output 2

0

The condition may already be satisfied from the beginning.

Sample Input 3

5
-2 -8 10 -2 2
3 5 1
1 3 5
2 5 0
3 4 6

Sample Output 3

28