GCD Path on a Tree
/

## 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

## This Problem was Asked in

Initializing Code Editor...