Great Cow Gathering

Interview

Time limit1sMemory limit128 MB

Summary

Pick a node of a weighted tree with node weights as the gathering point, and minimize the sum of cow count times distance to that node.

Level: Medium6 of 10
Topics: Tree, DFS, Dynamic programming, Prefix sum
Solved: No attempts yet

Problem

Bessie is planning the annual Great Cow Gathering and wants to choose the most convenient barn to host it.

Every cow lives in one of $N$ barns, numbered $1$ through $N$ . The barns are connected by $N-1$ roads so that you can travel between any two barns. Road $i$ connects barns $A_i$ and $B_i$ and has length $L_i$ ; the barns therefore form a tree. Barn $i$ is home to $C_i$ cows.

The gathering may be held in any single barn. If it is held in barn $X$ , its inconvenience is the total distance every cow must travel to reach $X$ : a barn holding $C_i$ cows at distance $d$ from $X$ contributes $C_i \cdot d$ . For example, if $3$ cows live in a barn $20$ units away from $X$ , they add $3 \times 20 = 60$ to the inconvenience.

Choose the barn that minimizes the total inconvenience, and report that minimum inconvenience.

Constraints

$1 \le N \le 100{,}000$
$1 \le A_i, B_i \le N$
$1 \le L_i \le 1{,}000$
$0 \le C_i \le 1{,}000$

Input

Line $1$ : a single integer $N$ .
Lines $2$ to $N+1$ : line $i+1$ contains a single integer $C_i$ , the number of cows in barn $i$ .
Lines $N+2$ to $2N$ : each of these $N-1$ lines contains three integers $A_i$ , $B_i$ , and $L_i$ , describing a road of length $L_i$ between barns $A_i$ and $B_i$ .

Output

A single line containing the minimum possible inconvenience.

Examples2

Example 1
Input
```
5
1
1
0
0
2
1 3 1
2 3 2
3 4 3
4 5 3
```
Expected output
```
15
```
Example 2
Input
```
2
1
1
1 2 5
```
Expected output
```
5
```