GCD Path on a Tree
Tag(s):

## Algorithms, Depth First Search, Dynamic programming, Graph, Medium-Hard

Problem
Editorial
Analytics

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

1. The number of vertices in the path should be a multiple of K.
2. 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$
SAMPLE INPUT
10 2
1 2
2 3
2 6
3 4
3 5
6 9
6 7
9 10
7 8
81 9 5 30 5 21 6 3 7 14

SAMPLE OUTPUT
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

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in Challenge Name

Airtel Crack the Code

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Dynamic Programming
• Algorithms > Graphs
• Algorithms > Graphs
• Algorithms > Greedy Algorithms
• Algorithms > String Algorithms