SOLVE

LATER

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

Initializing Code Editor...