MLE '19 Contest 3 P2 - Depression

View as PDF

Submit solution

Points: 12
Time limit: 2.0s
Memory limit: 1G

Problem types

You are given a tree consisting of N nodes and N-1 edges. Each edge has a weight w_i and each node as a value v_i. You can perform the following two operations on the tree any number of times:

  • Double a node u's value. In other words, v_u = v_u \times 2.
  • Take an edge k and divide (integer division) the edge's weight by the GCD (greatest common divisor) of the value of the nodes connected by the edge. In other words, w_k = \bigg\lfloor \frac{w_k}{GCD(a_k, b_k)} \bigg\rfloor, where a_k and b_k are the two nodes the edge connects.

After performing the above two operations any number of times, what is the minimum sum of all the edge weights and node values?

Input Specification

The first line will contain the integer N (1 \le N \le 10^5).

The next line will contain N integers, v_i (1 \le v_i \le 10^9).

The next N-1 lines will each contain three integers, a_j, b_j, w_j (1 \le a_j, b_j \le N, 1 \le w_j \le 10^9), meaning that nodes a_j and b_j will be connected by an edge of weight w_j. It is guaranteed that the tree will be fully connnected.

Output Specification

Output the minimum sum of all the edge weights and node values after performing the above operations any number of times.

Sample Input

3 2 1
1 2 10
2 3 9

Sample Output



There are no comments at the moment.