All Tracks Algorithms Graphs Depth First Search Problem

Longest Path
Tag(s):

Algorithms, Depth First Search, Depth-first search, Graph, Medium

Problem
Editorial
Analytics

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\)

SAMPLE INPUT
6 2
4 2 3 2 3 5
1 2
1 3
2 4
2 5
3 6
SAMPLE OUTPUT
2
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
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...
Your Rating:

Contributor

This Problem was Asked in

Airtel

Challenge Name

Airtel Crack the Code

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?