You are given a tree with $n$ vertices. Each edge has a weight, and each vertex has a label. We denote the label of vertex $i$ as $label(i)$.
A simple path from vertex $s$ to vertex $t$ is defined as an ordered sequence of vertices $v_0 \rightarrow v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_ k$, where $v_0 = s, v_ k = t$, and all $v_ i$ are unique. For each valid index $i$, $v_ i$ and $v_{i+1}$ are connected directly by an edge. Note that there exists a simple path between every pair of vertices in a tree.
We define:
$dist(u, v)$ as the sum of the weight of all edges on the simple path from $u$ to $v$.
$greatness(u, v) = dist(u, v) \cdot gcd(label(u), label(v))$.
Please find the two different vertices $u$ and $v$ with maximum $greatness(u, v)$.
The input contains multiple test cases, each test case is presented as below:
The first line contains a single integer $n$ $(2 \le n \le 10^5)$. The sum of $n$ among all test cases does not exceed $10^5$.
The second line contains $n$ integers, the $i$-th integer is $label(i)$ $(1 \le label(i) \le 5 \cdot 10^5)$.
In the next $n-1$ lines, each line contains three integers $u$, $v$ and $w$ $(1 \le u, v \le n, 1 \le w \le 10^6)$ describing an edge of weight $w$ connecting two vertices $u$ and $v$.
The input ends with a line containing a single $0$ which is not a test case.
For each test case, print a single line containing the maximum value of $greatness(u, v)$.
Sample Input 1 | Sample Output 1 |
---|---|
2 10 10 1 2 10 0 |
100 |