Maximum Tree Path

All submissions for this problem are available.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well.
You're given a tree with N vertices. There is a positive integer written in each vertex; let's denote the integer written in vertex i by A_{i}.
Consider a simple path between vertices u and v. Let's define dist(u, v) as the length of the path, gcd(u, v) as the greatest common divisor of all numbers written in vertices that lie on the path (including u and v) and min(u, v) as the minimum of numbers written in vertices on the path (including u and v).
Compute the maximum of the expression dist(u, v) · gcd(u, v) · min(u, v) over all pairs of vertices (u, v).
Input
 The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
 The first line of each test case contains a single integer N denoting the number of vertices of the tree.
 The second line contains N spaceseparated integers A_{1}, A_{2}, ..., A_{N}.
 Each of the following N1 lines contains three spaceseparated integers u, v and w denoting an edge with length w between vertices u and v.
Output
For each testcase, print a single line containing one integer — the answer to the problem.
Constraints
 1 ≤ T ≤ 100
 2 ≤ N ≤ 10^{5}
 2 ≤ sum of N over all test cases ≤ 10^{5}
 1 ≤ A_{i} ≤ 10^{4} for each valid i
 1 ≤ u, v ≤ N
 1 ≤ w ≤ 10^{5}
Example
Input: 1 4 1 2 3 4 1 2 1 1 3 2 3 4 3 Output: 9
Author:  chemthan 
Editorial  https://discuss.codechef.com/problems/MXPATH 
Tags  chemthan, cook92, datastructure, mediumhard, tree 
Date Added:  19022018 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions