All Tracks Algorithms Graphs Depth First Search Problem

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

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?