SOLVE

LATER

Longest Path

/

You are given a tree with \(N\) nodes and **\(N-1\)** edges and an integer \(K\). Each node has a label denoted by an integer, **\(A_i\)**. Your task is to find the length of the longest path such that label of all the nodes in the path are divisible by** \(K\)**.

Length of a path is the number of edges in that path.

**Input Format: **

First line contains two space separated integers, \(N\) and \(K\). Next line contains \(N\) space separated integers, \(i^{th}\) integer denotes the label of \(i^{th}\) node, \(A_i\). Next \(N-1\) lines contains two space separated integers each, \(U\) and \(V\) denoting that there is an edge between node \(U\) and node \(V\).

**Output Format:**

Print a single integer denoting the length of the longest path such that label of all the nodes in the path are divisible by \(K\).

**Constraints:**

\(1 \le N \le 10^5\)

\(1 \le K \le 10^5\)

\(1 \le A_i \le 10^5\)

\(1 \le U, V \le N\)

Explanation

Longest path will be 1->2->4.

Time Limit:
1.0 sec(s)
for each input file.

Memory Limit:
256 MB

Source Limit:
1024 KB

Initializing Code Editor...