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 Ai.
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).
- 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 space-separated integers A1, A2, ..., AN.
- Each of the following N-1 lines contains three space-separated integers u, v and w denoting an edge with length w between vertices u and v.
For each testcase, print a single line containing one integer — the answer to the problem.
- 1 ≤ T ≤ 100
- 2 ≤ N ≤ 105
- 2 ≤ sum of N over all test cases ≤ 105
- 1 ≤ Ai ≤ 104 for each valid i
- 1 ≤ u, v ≤ N
- 1 ≤ w ≤ 105
Input: 1 4 1 2 3 4 1 2 1 1 3 2 3 4 3 Output: 9
|Tags||chemthan, cook92, datastructure, medium-hard, tree|
|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, PYP3, CLOJ, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.