GCD Path on a Tree
Given an Integer K and a tree of N vertices where each vertex consists of a value \(V_i\) associated to it. Find the longest path in the tree which satisfies the following conditions
- The number of vertices in the path should be a multiple of K.
- Let's say there are \(L \times K\) vertices in the path and \(X_i\) be the value associated with \(i^{th}\) vertex in that path, then \(gcd( X_{i \times K+1}\), \(X_{i \times K+2}\), \(X_{i \times K+3}\), ... \(X_{i \times K+K}) > 1\) \(\forall i \in [0, L-1].\) where \(gcd(x1, x2 ... xn)\) is the Greatest Common Divisor of the numbers \(x1,x2... xn\).
Input Format
First line consists of two integers N and K.
Next \(N-1\) lines consists of two integers \(u_i\) and \(v_i\) representing an edge between \(u_i\) and \(v_i\).
Next line consists of N space separated integers where \(i^{th}\) of them is the value \(V_i\) associated to \(i^{th}\) vertex.
Output Format
Print an Integer representing the longest path as described in the problem statement.
Constraints
- \(1 \le N \le 10^5\)
- \(1 \le K \le min(N,10)\)
- \(1 \le V_i \le 10^6\)
Explanation
Longest Path is \(4-3-2-6-7-8\) of length 6
\(gcd(V_4,V_3) = gcd(30,5) = 5 > 1\)
\(gcd(V_2,V_6) = gcd(9,21) = 3 > 1\)
\(gcd(V_7,V_8) = gcd(6,3) = 3 > 1\)
Time Limit:
2.0 sec(s)
for each input file.
Memory Limit:
256 MB
Source Limit:
1024 KB
Marking Scheme:
Marks are awarded when all the testcases pass.
Allowed Languages:
Bash,
C,
C++,
C++14,
Clojure,
C#,
D,
Erlang,
F#,
Go,
Groovy,
Haskell,
Java,
Java 8,
JavaScript(Rhino),
JavaScript(Node.js),
Julia,
Kotlin,
Lisp,
Lisp (SBCL),
Lua,
Objective-C,
OCaml,
Octave,
Pascal,
Perl,
PHP,
Python,
Python 3,
R(RScript),
Racket,
Ruby,
Rust,
Scala,
Swift,
Swift-4.1,
TypeScript,
Visual Basic