Given an undirected and connected graph of N vertices and N-1 edges. The number written on the ith vertex is val[i]. The task is to count the number of pairs (x, y) such that following conditions are satisfied:
- 0 ≤ x < y ≤ N-1
- The GCD of the numbers written on the vertices on the simple path in the given graph from x to y should be divisible by K.
Example:
Input:
N = 4, K = 2
Edges[] = {{0, 1}, {0, 2}, {2, 3}}
Val[] = {2, 6, 4, 3}
Output:
3
Explanation:
0 - 1
|
2 - 3
There are three pairs - (0,1), (1,2) and
(0,2) which satisify both the conditions.
There are two observations here:
1)It is a connected graph and it has n-1 edges. So it has to be a tree.
2)For condition 2 to be true, all the numbers written on the nodes in the simple path between x and y has to be k or a multiple of k.
With these two observations we can devise a solution
Replace all val[i]'s with val[i]%k.
Foreach i from 0 to n-1:
a. if val[i]==0, and not visited before Run a dfs from node i.
b. In dfs only visit the nodes for which val[node]=0 and not visited before. Return the number of nodes you visited on this run. Let this number be x. Also mark these nodes visited.
c. Add xC2 = (x*(x-1))/2 to the answer. (Why? because all the pairs of these visited nodes satisfies both of our conditions. We can select 2 nodes in xC2 ways.).