There is a tree (i.e.,&nbsp;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.

&nbsp;
Example 1:



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:



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]


&nbsp;
Constraints:


	nums.length == n
	1 &lt;= nums[i] &lt;= 50
	1 &lt;= n &lt;= 105
	edges.length == n - 1
	edges[j].length == 2
	0 &lt;= uj, vj &lt; n
	uj != vj


class Solution:
    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:
        
        gcdset = [set() for i in range(51)]
        for i in range(1,51):
            for j in range(1,51):
                if math.gcd(i,j) == 1:
                    gcdset[i].add(j)
                    gcdset[j].add(i)
        
        graph = defaultdict(list)
        for v1, v2 in edges:
            graph[v1].append(v2)
            graph[v2].append(v1)
        
        ans = [-1]*len(nums)
        q = [[0, {}]]
        seen = set([0])
        depth = 0
        while q:
            temp = []
            for node, ancestors in q:
                index_depth = (-1,-1)
                for anc in list(ancestors.keys()):
                    if anc in gcdset[nums[node]]:
                        index, d = ancestors[anc]
                        if d > index_depth[1]:
                            index_depth = (index,d)
                ans[node] = index_depth[0]
                
                copy = ancestors.copy()
                copy[nums[node]] = (node,depth)
                
                for child in graph[node]:
                    if child not in seen:
                        seen.add(child)
                        temp.append([child, copy])
            q = temp
            depth += 1
        return ans
class Solution {
    //made TreeNode class for simple implementation in recurring function
    class TreeNode{
        int id;
        int val;
        List<TreeNode> child;
        public TreeNode(int id,int val){
            this.id=id;this.val=val;child=new ArrayList<>();
        }
    }
    public int[] getCoprimes(int[] nums, int[][] edges) {
        // making tree/graph with edges
        TreeNode[] tr=new TreeNode[nums.length];
        for(int i=0;i<nums.length;i++)tr[i]=new TreeNode(i,nums[i]);
        for(int []x:edges){
            tr[x[0]].child.add(tr[x[1]]);
            tr[x[1]].child.add(tr[x[0]]);
        }
        // intializing answer array of length of tree's nodes which we will return
        int [] ans=new int[nums.length];
        Arrays.fill(ans,-1);
        //creating gcd to not compute gcd everytime
        boolean [][] gcd=new boolean[51][51];
        for(int i=1;i<=50;i++){
            for(int j=i;j<=50;j++){
                if(find_gcd(i,j)==1){
                    gcd[i][j]=true;
                    gcd[j][i]=true;
                }
            }
        }
        int [][] latest= new int[51][2];
		//instead of latest[][] as 2d array we can also use 2 arrays, one for who is latest ancestor & one for storing id
        // in [][0] we will store height of tree so latest ancestor will be called
        // in [][1] we will store id of latest tree
        // initializing all to -1
        for(int i=0;i<=50;i++){latest[i][0]=-1;latest[i][1]=-1;}
        find_closest_ancestor(tr[0],new TreeNode(-1,-1),ans,latest,gcd,0);
        return ans;
    }
    public void find_closest_ancestor(TreeNode root,TreeNode parent, int[] ans,int [][] latest, boolean [][] gcd, int height){
        int val=root.val;
        int latest_id=0;
        for(int i=1;i<=50;i++){
            //if gcd [val][i] is true & latest[i][0] is latest ancestor i.e. it's height is more then save that id
            if(gcd[val][i] && latest[latest_id][0] < latest[i][0])latest_id=i;
        }
        ans[root.id]=latest[latest_id][1];// even if no latest ancestor found latest[id][1] is -1 by default
        
        //this is must we will save before state & after calling all it's child we will make it as it was before calling
        //like backtracking
        int pre_height = latest[val][0],pre_id = latest[val][1];
        latest[val][0]=height;  latest[val][1]=root.id;
        
        // we recur with all child
        for(TreeNode root_child: root.child){
            // we will check if we aren't going upward in tree so root.child!=parent then call function
            if(root_child!=parent)find_closest_ancestor(root_child,root,ans,latest,gcd,height+1);
        }
        //as it was before we will put it back
        latest[val][0]=pre_height;  latest[val][1]=pre_id;
    }
    //simple gcd code
    public int find_gcd(int a, int b){
        if(b==0)return a;
        return find_gcd(b,a%b);
    }
}
class Solution {
public:
    vector<int> adj[100009];
    vector<int> d[55];
    int dis[100009];
    void dfs(vector<int>& nums,vector<int> &ans,int i,int p,int h1)
    {
        int h=nums[i];
        dis[i]=h1;
        ans[i]=-1;
        int val=-1;
        for(int w=1;w<=50;w++)
        {
            if(__gcd(h,w)==1)
            {
                if(d[w].size())
                {
                    int u=d[w].back();
                    if(dis[u]>val)
                    {
                        val=dis[u];
                        ans[i]=u;
                    }
                }
            }
        }
        d[h].push_back(i);
        for(auto x:adj[i])
        {
            if(x==p) continue;
            dfs(nums,ans,x,i,h1+1);
        }
        d[h].pop_back();
    }
    vector<int> getCoprimes(vector<int>& nums, vector<vector<int>>& edges) {
        int n=nums.size();
        for(int i=0;i<n;i++)
        {
            adj[i].clear();
        }
        for(int i=0;i<n-1;i++)
        {
            adj[edges[i][0]].push_back(edges[i][1]);
            adj[edges[i][1]].push_back(edges[i][0]);
        }
        vector<int> ans(n);
        dfs(nums,ans,0,-1,0);
        return ans;
    }
};
var getCoprimes = function(nums, edges) {
    
    const node = {}
    const ans = Array(nums.length).fill(null)
    
    function addNode(f, t){
        if(!node[f]){
            node[f]=[]
        }
        node[f].push(t)
    }
    
    edges.forEach(([f, t])=>{
        addNode(f, t)
        addNode(t, f)
    })
    
    function gcd(a, b){
        while(b) [a, b] = [b, a % b];
        return a;
    }
    
    const map = []
    for(let i=0; i<51; i++){
        map[i]=[]
        for(let j=0; j<51; j++){
            map[i][j]= gcd(i,j)
        }
    }

    let pi=-1
    let path=Array(nums.length)
    function check(v){
        if(ans[v]!==null) return
        ans[v] = -1
        let a = nums[v]
        for(let k=pi; k>=0; k--){
            let b = nums[path[k]]
            if(map[a][b]===1){
                ans[v]=path[k]
                break
            }
        }
        if(node[v]) {
            path[++pi]=v
            node[v].forEach(child=>check(child))
            pi--
        }
    }
    
    for(let i=0; i<nums.length; i++){
        check(i)
    }
    
    return ans    
};
Tree of Coprimes