# Tree of Coprimes
**Difficulty:** HARD
[External](https://leetcode.com/problems/tree-of-coprimes)
Canonical: https://scaleengineer.com/dsa/problems/tree-of-coprimes
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory)
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Array, Tree
---
## Problem
There is a tree (i.e., a connected, undirected graph that has no cycles) consisting of `n` nodes numbered from `0` to `n - 1` and exactly `n - 1` edges. Each node has a value associated with it, and the **root** of the tree is node `0`.

To represent this tree, you are given an integer array `nums` and a 2D array `edges`. Each `nums[i]` represents the `ith` node's value, and each `edges[j] = [uj, vj]` represents an edge between nodes `uj` and `vj` in the tree.

Two values `x` and `y` are **coprime** if `gcd(x, y) == 1` where `gcd(x, y)` is the **greatest common divisor** of `x` and `y`.

An ancestor of a node `i` is any other node on the shortest path from node `i` to the **root**. A node is **not** considered an ancestor of itself.

Return _an array_ `ans` _of size_ `n`, _where_ `ans[i]` _is the closest ancestor to node_ `i` _such that_ `nums[i]` _and_ `nums[ans[i]]` are **coprime**, or `-1` _if there is no such ancestor_.

**Example 1:**

**![](https://assets.glich.co/dsa/tree-of-coprimes/image0.png)**

**Input:** nums = [2,3,3,2], edges = [[0,1],[1,2],[1,3]]
**Output:** [-1,0,0,1]
**Explanation:** In the above figure, each node's value is in parentheses.
- Node 0 has no coprime ancestors.
- Node 1 has only one ancestor, node 0. Their values are coprime (gcd(2,3) == 1).
- Node 2 has two ancestors, nodes 1 and 0. Node 1's value is not coprime (gcd(3,3) == 3), but node 0's
  value is (gcd(2,3) == 1), so node 0 is the closest valid ancestor.
- Node 3 has two ancestors, nodes 1 and 0. It is coprime with node 1 (gcd(3,2) == 1), so node 1 is its
  closest valid ancestor.

**Example 2:**

![](https://assets.glich.co/dsa/tree-of-coprimes/image1.png)

**Input:** nums = [5,6,10,2,3,6,15], edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]]
**Output:** [-1,0,-1,0,0,0,-1]

**Constraints:**

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

# Approaches
## Brute-Force Traversal to Root
This straightforward approach iterates through each node and, for each one, traverses up the tree towards the root. It checks every ancestor along this path. The first ancestor found to have a value coprime with the current node's value is guaranteed to be the closest one, so it's recorded as the answer.
**Time:** O(N * H), where N is the number of nodes and H is the height of the tree. The pre-computation of parents takes O(N). The main loop runs N times, and in each iteration, it can traverse up to H ancestors. In the worst case of a skewed tree, H is O(N), leading to an overall complexity of O(N^2). · **Space:** O(N), where N is the number of nodes. This space is used to store the adjacency list and the `parent` array.
**Pros:** Conceptually simple and easy to implement.; Correctly finds the closest ancestor due to the bottom-up search direction.
**Cons:** The time complexity is too high for the given constraints (N up to 10^5), as it can be quadratic in the number of nodes.; It performs a lot of redundant computations, as the ancestor paths of sibling nodes are re-traversed repeatedly.
### Explanation
To implement this, we first need an efficient way to move from a node to its parent. We can pre-process the tree by performing a Breadth-First Search (BFS) or Depth-First Search (DFS) from the root (node 0) to populate a `parent` array. `parent[i]` will store the parent of node `i`, with `parent[0]` being -1.

Once the `parent` array is built, the main part of the algorithm begins. It loops through every node `i` in the tree. For each node, it initiates another loop that starts from `i`'s parent and travels up the chain of ancestors using the `parent` array. In each step of this upward traversal, it calculates the Greatest Common Divisor (GCD) between the value of node `i` and the value of the current ancestor. If the GCD is 1, the two values are coprime. Since we are moving up from the immediate parent, the first such ancestor we find is the closest one. We record its index in our answer array and stop the search for node `i`. If the traversal reaches the root's parent (-1) without finding any coprime ancestor, the answer for node `i` remains -1.

```java
class Solution {
    public int[] getCoprimes(int[] nums, int[][] edges) {
        int n = nums.length;
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }

        int[] parent = new int[n];
        Arrays.fill(parent, -1);
        Queue<Integer> q = new LinkedList<>();
        q.offer(0);
        boolean[] visited = new boolean[n];
        visited[0] = true;

        while (!q.isEmpty()) {
            int u = q.poll();
            for (int v : adj.get(u)) {
                if (!visited[v]) {
                    visited[v] = true;
                    parent[v] = u;
                    q.offer(v);
                }
            }
        }

        int[] ans = new int[n];
        Arrays.fill(ans, -1);

        for (int i = 0; i < n; i++) {
            int currAncestor = parent[i];
            while (currAncestor != -1) {
                if (gcd(nums[i], nums[currAncestor]) == 1) {
                    ans[i] = currAncestor;
                    break;
                }
                currAncestor = parent[currAncestor];
            }
        }
        return ans;
    }

    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}
```
### Algorithm
- First, build a `parent` array where `parent[i]` stores the parent of node `i`. This can be done with a single BFS or DFS traversal starting from the root (node 0).
- Initialize an `ans` array of size `n` with `-1`.
- Iterate through each node `i` from 1 to `n-1` (node 0 has no ancestors).
- For each node `i`, start an upward traversal from its immediate parent, let's call it `ancestor = parent[i]`.
- In a `while` loop that continues as long as `ancestor` is valid (not -1):
    - Check if `nums[i]` and `nums[ancestor]` are coprime using the Greatest Common Divisor (GCD) function.
    - If they are coprime, we have found the closest such ancestor because we are traversing upwards. Set `ans[i] = ancestor` and break the inner loop.
    - If not, move to the next ancestor: `ancestor = parent[ancestor]`.
- After checking all nodes, return the `ans` array.

## DFS with Path History
This approach uses a single Depth-First Search (DFS) from the root. During the traversal, it maintains the list of nodes on the current path from the root to the node being visited. For each node, it then searches backwards along this path to find the closest ancestor with a coprime value.
**Time:** O(N * H), where H is the tree height. At each node at depth `d`, the algorithm iterates through `d` ancestors. The total work is the sum of the depths of all nodes, which is O(N*H) in general and O(N^2) for a skewed tree. · **Space:** O(H^2) in the worst case, where H is the tree height. The recursion stack can go H deep, and the path list at depth `d` has size `d`. The total space for paths on the stack can be O(H^2), which is O(N^2) for a skewed tree.
**Pros:** Organizes the search within a single, structured tree traversal.; Avoids the need for a separate pre-computation step to find parents.
**Cons:** Still has a worst-case time complexity of O(N^2), which is too slow.; The space complexity is also poor. In a skewed tree, the recursion depth and the size of the path list can both be O(N), leading to O(N^2) space usage due to path copies on the recursion stack.
### Explanation
The algorithm begins by setting up an adjacency list for the tree. A recursive DFS function is the core of this method. This function takes the current node, its parent, and, crucially, a list representing the current path of ancestors.

When the DFS visits a node `u`, it examines the `path` list. By iterating through this list in reverse order (from end to beginning), it checks ancestors starting from the closest one (the parent) and moving towards the root. For each ancestor, it computes the GCD with `u`'s value. The first one that results in a GCD of 1 is the desired closest coprime ancestor. Its index is recorded, and the search for `u` concludes.

To continue the traversal, the current node `u` is appended to the path list. The DFS function is then called recursively for all of `u`'s children. An essential step is backtracking: after the recursive calls for a node's subtree are complete, that node must be removed from the path list. This ensures that when the traversal moves to a sibling branch, the path correctly reflects the ancestor chain.

```java
class Solution {
    List<List<Integer>> adj;
    int[] nums;
    int[] ans;

    public int[] getCoprimes(int[] nums, int[][] edges) {
        int n = nums.length;
        this.nums = nums;
        this.ans = new int[n];
        Arrays.fill(ans, -1);
        
        adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }

        dfs(0, -1, new ArrayList<>());
        return ans;
    }

    private void dfs(int u, int p, List<Integer> path) {
        int closestAncestor = -1;
        for (int i = path.size() - 1; i >= 0; i--) {
            int ancestorNode = path.get(i);
            if (gcd(nums[u], nums[ancestorNode]) == 1) {
                closestAncestor = ancestorNode;
                break;
            }
        }
        ans[u] = closestAncestor;

        path.add(u);
        for (int v : adj.get(u)) {
            if (v != p) {
                dfs(v, u, path);
            }
        }
        path.remove(path.size() - 1); // Backtrack
    }

    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}
```
### Algorithm
- Build an adjacency list representation of the tree.
- Initialize an `ans` array of size `n` with `-1`.
- Define a recursive DFS function, `dfs(node, parent, path)`, where `path` is a list of nodes from the root to the current `node`'s parent.
- Inside the `dfs` function for a node `u`:
    - Iterate backwards through the `path` list, from the last element (closest ancestor) to the first.
    - For each `ancestorNode` in the path, check if `gcd(nums[u], nums[ancestorNode]) == 1`.
    - If they are coprime, set `ans[u] = ancestorNode` and break the loop.
- Before recursing to children, add the current node `u` to the `path`.
- Call `dfs` for all children of `u`.
- After the recursive calls return, remove `u` from the `path` to backtrack, ensuring the path is correct for sibling nodes.
- Start the process by calling `dfs(0, -1, new ArrayList<>())`.

## Optimized DFS with Ancestor Value Tracking
This optimal approach capitalizes on the constraint that node values are small (1 to 50). It performs a single DFS traversal, but instead of passing the entire ancestor path, it maintains a small, constant-size data structure that tracks the most recent ancestor seen for each possible value. This avoids the expensive search through the ancestor list at each node.
**Time:** O(N * M), where N is the number of nodes and M is the maximum possible value in `nums` (M=50). The DFS visits each node once, and at each node, it performs a constant amount of work (a loop of size M and GCD calculations). · **Space:** O(N + M), where N is the number of nodes and M is the max value (50). This includes O(N) for the adjacency list, O(H) for the recursion stack (where H <= N), and O(M) for the `ancestorInfo` array.
**Pros:** Highly efficient with a time complexity linear in the number of nodes.; Effectively uses the problem's constraint on the range of node values.; Optimal solution that will pass for large inputs.
**Cons:** The logic is more complex than brute-force, requiring careful state management (saving and restoring) to ensure correctness during backtracking.
### Explanation
The key insight is that for a given node `u`, we only need to know, for each value `v` from 1 to 50, the location of the *deepest* ancestor that has that value. This is because the deepest ancestor is also the closest one.

We use an array, `ancestorInfo`, of size 51. `ancestorInfo[v]` will store the depth and index of the most recent ancestor with value `v` encountered on the current DFS path. During the traversal, when we visit a node `u` at a certain `depth`, we can find its answer efficiently. We iterate through all possible values `v` from 1 to 50. If `v` is coprime with `nums[u]`, we look up `ancestorInfo[v]`. We keep track of the coprime ancestor candidate that has the maximum depth; this will be our answer for `u`.

The most critical part is state management for the DFS. Before the DFS recurses into the children of `u`, we must update the state to include `u` as a potential ancestor. We do this by updating `ancestorInfo[nums[u]]` with `u`'s depth and index. However, this change should only be visible to `u`'s descendants. Therefore, after the recursive calls for `u`'s children have completed, we must revert `ancestorInfo[nums[u]]` to its previous state. This backtracking step ensures that when the traversal moves to `u`'s siblings, `u` is correctly not considered an ancestor.

```java
class Solution {
    List<List<Integer>> adj;
    int[] nums;
    int[] ans;
    int[][] ancestorInfo; // {depth, node_index} for each value 1-50

    public int[] getCoprimes(int[] nums, int[][] edges) {
        int n = nums.length;
        this.nums = nums;
        this.ans = new int[n];
        Arrays.fill(ans, -1);
        
        this.ancestorInfo = new int[51][2]; 
        for(int i=0; i<51; i++) {
            ancestorInfo[i][0] = -1; // depth
            ancestorInfo[i][1] = -1; // node index
        }

        adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }

        dfs(0, -1, 0);
        return ans;
    }

    private void dfs(int u, int p, int depth) {
        int maxDepth = -1;
        int closestAncestor = -1;

        for (int val = 1; val <= 50; val++) {
            if (ancestorInfo[val][0] > -1) { // Check if an ancestor with this value exists
                if (gcd(nums[u], val) == 1) {
                    if(ancestorInfo[val][0] > maxDepth) {
                        maxDepth = ancestorInfo[val][0];
                        closestAncestor = ancestorInfo[val][1];
                    }
                }
            }
        }
        ans[u] = closestAncestor;

        int[] oldState = ancestorInfo[nums[u]];
        ancestorInfo[nums[u]] = new int[]{depth, u};

        for (int v : adj.get(u)) {
            if (v != p) {
                dfs(v, u, depth + 1);
            }
        }

        ancestorInfo[nums[u]] = oldState;
    }

    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}
```
### Algorithm
- Build an adjacency list for the tree.
- Create an auxiliary data structure, `ancestorInfo`, which is an array of size 51. `ancestorInfo[v]` will store a pair `{depth, node_index}` for the most recent ancestor with value `v`.
- Initialize all entries in `ancestorInfo` to a sentinel value like `{-1, -1}`.
- Define a recursive DFS function `dfs(u, parent, depth)`.
- Inside `dfs(u, parent, depth)`:
    - Find the closest coprime ancestor for `u`. Initialize `maxDepth = -1` and `closestAncestor = -1`.
    - Iterate through all possible values `v` from 1 to 50.
    - If `gcd(nums[u], v) == 1`, check `ancestorInfo[v]`. If its depth is greater than `maxDepth`, update `maxDepth` and `closestAncestor` with the information from `ancestorInfo[v]`.
    - After checking all 50 values, set `ans[u] = closestAncestor`.
    - **Update State:** Before recursing, save the current state of `ancestorInfo[nums[u]]`. Then, update `ancestorInfo[nums[u]]` with the current node's information: `{depth, u}`.
    - **Recurse:** Call `dfs` for all children of `u`.
    - **Backtrack:** After the recursive calls return, restore `ancestorInfo[nums[u]]` to its saved state.
- Start the traversal with `dfs(0, -1, 0)`.

# Solutions
### Java

```java
class Solution {
private
  List<Integer>[] g;
private
  List<Integer>[] f;
private
  Deque<int[]>[] stks;
private
  int[] nums;
private
  int[] ans;
public
  int[] getCoprimes(int[] nums, int[][] edges) {
    int n = nums.length;
    g = new List[n];
    Arrays.setAll(g, k->new ArrayList<>());
    for (var e : edges) {
      int u = e[0], v = e[1];
      g[u].add(v);
      g[v].add(u);
    }
    f = new List[51];
    stks = new Deque[51];
    Arrays.setAll(f, k->new ArrayList<>());
    Arrays.setAll(stks, k->new ArrayDeque<>());
    for (int i = 1; i < 51; ++i) {
      for (int j = 1; j < 51; ++j) {
        if (gcd(i, j) == 1) {
          f[i].add(j);
        }
      }
    }
    this.nums = nums;
    ans = new int[n];
    dfs(0, -1, 0);
    return ans;
  }
private
  void dfs(int i, int fa, int depth) {
    int t = -1, k = -1;
    for (int v : f[nums[i]]) {
      var stk = stks[v];
      if (!stk.isEmpty() && stk.peek()[1] > k) {
        t = stk.peek()[0];
        k = stk.peek()[1];
      }
    }
    ans[i] = t;
    for (int j : g[i]) {
      if (j != fa) {
        stks[nums[i]].push(new int[]{i, depth});
        dfs(j, i, depth + 1);
        stks[nums[i]].pop();
      }
    }
  }
private
  int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> getCoprimes(vector<int> &nums, vector<vector<int>> &edges) {
    int n = nums.size();
    vector<vector<int>> g(n);
    vector<vector<int>> f(51);
    vector<stack<pair<int, int>>> stks(51);
    for (auto &e : edges) {
      int u = e[0], v = e[1];
      g[u].emplace_back(v);
      g[v].emplace_back(u);
    }
    for (int i = 1; i < 51; ++i) {
      for (int j = 1; j < 51; ++j) {
        if (__gcd(i, j) == 1) {
          f[i].emplace_back(j);
        }
      }
    }
    vector<int> ans(n);
    function<void(int, int, int)> dfs = [&](int i, int fa, int depth) {
      int t = -1, k = -1;
      for (int v : f[nums[i]]) {
        auto &stk = stks[v];
        if (!stk.empty() && stk.top().second > k) {
          t = stk.top().first;
          k = stk.top().second;
        }
      }
      ans[i] = t;
      for (int j : g[i]) {
        if (j != fa) {
          stks[nums[i]].push({i, depth});
          dfs(j, i, depth + 1);
          stks[nums[i]].pop();
        }
      }
    };
    dfs(0, -1, 0);
    return ans;
  }
};

```

### Python

```python
class Solution:
    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]: def dfs(i, fa, depth): t = k = - 1 for v in f[nums[i]]: stk = stks[v] if stk and stk[- 1][1] > k: t, k = stk[- 1] ans[i] = t for j in g[i]: if j != fa: stks[nums[i]]. append((i, depth)) dfs(j, i, depth + 1) stks[nums[i]]. pop() g = defaultdict(list) for u, v in edges: g[u]. append(v) g[v]. append(u) f = defaultdict(list) for i in range(1, 51): for j in range(1, 51): if gcd(i, j) == 1: f[i]. append(j) stks = defaultdict(list) ans = [- 1] * len(nums) dfs(0, - 1, 0) return ans

```