Company: HandsOn_30_dec
Difficulty: medium
Count Good Paths 2. Count Good Paths Description You are given a tree (i.e., a connected, undirected graph with no cycles) consisting of n nodes numbered from 0 to n - 1 and exactly n - 1 edges. You are also given a 0-indexed integer array vals of length n , where vals[i] is the value associated with the i th node. A path is a sequence of nodes in the tree. A path is considered good if the greatest common divisor (GCD) of the values of all nodes in that path is equal to 1 . A path can consist of a single node. The path from node u to v is the same as the path from v to u . Return the total number of different good paths . Example 1: Input: vals = [1,1,1,1,1], edges = [[0,1],[1,2],[2,3],[3,4]] Output: 15 Explanation: Given n = 5, vals = [1,1,1,1,1], and the edges form a line graph. Since all node values are 1, the GCD of the values on any path will be 1. The total number of possible paths in a tree with 5 nodes is 15. The paths are (0,0), (1,1), (2,2), (3,3), (4,4), (0,1), (0,2), (0,3),