Like many other problems, let's figure out the input, limitation and output from the description.

- The input of this problem is a tree where each node has a value. It is given by an array
**nums**representing values of each node. And**edges**representing the edge between the**edge[i][0]**and**edge[i][1]**. - The limitation is given by the definition
**Coprime**, where the greatest common divisor(GCD) of 2 node values is**1**. - The required output is the
**closest coprime anacestor**for each node. The result should be returned by an array where**result[i]**is the*index*of node i's closest coprime anacestor.

Even if the input is a tree, since we are only given **edges**, we can use **adjacent list** to
represent the tree, where adj[i] is a list of nodes who is node i's neighbors.

The basic idea of this problem is to traverse the tree. And during the traversal, for each node, calculate the closest coprime anacestor. Now let's consider the time complexity of this basic solution.

- To traverse a tree, we can use Depth-first Search (DFS). The basic time complexity of DFS is O(nodes.length + edges.length).
- For each node, we need to go through all it's ancestors from bottom to top to check if they are coprime. The worst case would be there are no coprime in it's ancestors, and the time complexity of this step would be O(tree.depth). Since the tree is not a balanced tree, for it's depth, we need to consider it's the same as node number, which is O(nodes.length).
- To check if 2 numbers are coprime, we would need to check all number which is less than or equal to the minimum number between the 2 numbers, to see if it's a common divisor of them. Time complexity of this step is O(num).

The overall time complexity would be:

O((nodes.length + edges.length) * nodes.length * max(nums))

The input range is given in the problem description.

- nums.length == n
- 1 <= nums[i] <= 50
- 1 <= n <= 100,000
- edges.length == n - 1
- edges[j].length == 2
- 0 <= uj, vj < n
- uj != vj

And the number of operations is:

O( (n + n) * n * len(nums) ) = O( n ** 2 * len(nums) ) = O( (10 ** 10) * 50 ) = O( 10 ** 11 )

This is high above standard which is **1,000,000**.

The basic solution spend too much time because there are too many operations. In this case, we can consider to pre-calculate something. So the time complexity would be O(pre) + O(solution).

- One key point of this problem is that the range of each number is between
**1**and**50**. So

we could calculate isCoprime for all integer pairs in time O(max(nums) ** 2) = O(2,500).

- Then, for each node, instead of calculate through all it's ancestors, we maintain a array storing

the closest anacestor for each number. And update this array for each node. This would only take O(max(nums)).

So now, the time complexity is:

O(max(nums) ** 2) + O(n + n) * O(max(nums)) = O(max(nums) ** 2) + O( n * max(nums) ) = O( max(nums) * (max(nums) + n) ) = O( 50 * (50 + 100,000) ) ~= O( 5 * (10 ** 6) ) = O( 5,000,000 )

This would be a **just fine** time time complexity (around 1,000,000).

- The method
**isCoprime**is for calculating whether 2 numbers are coprime. - The method
**_dfs**is the main part of the solution, which traverses the tree and calculate the closest coprime ancestor. - Variable
**candidates**stores the cloeset coprime ancestor for each possible number, it's maximum length is 50.

```
class Solution:
def getCoprimes(self, nums, edges):
candidates = set(nums)
coprime = {}
for i in candidates:
for j in candidates:
coprime[(i, j)] = self.isCoprime(i, j)
adj = [[] for _ in range(len(nums))]
for p, q in edges:
adj[p].append(q)
adj[q].append(p)
closestCoprime = [-1] * len(nums)
candidates = {v: -1 for v in set(nums)}
self._dfs(-1, 0, nums, adj, candidates, closestCoprime, coprime)
return closestCoprime
def isCoprime(self, i, j):
if i == 1 or j == 1:
return True
if i == j:
return False
for c in range(2, min(i, j) + 1):
if i % c == 0 and j % c == 0:
return False
return True
def _dfs(self, parent, current, nums, adj, candidates, closestCoprime, coprime):
closestCoprime[current] = candidates[nums[current]]
tmp = {}
for key in candidates.keys():
if coprime[(nums[current], key)]:
tmp[key] = candidates[key]
candidates[key] = current
for child in adj[current]:
if child == parent:
continue
self._dfs(current, child, nums, adj, candidates, closestCoprime, coprime)
for key in tmp.keys():
candidates[key] = tmp[key]
```