1
class Solution {
2
  // made TreeNode class for simple implementation in recurring function
3
  class TreeNode {
4
    int id;
5
    int val;
6
    List<TreeNode> child;
7

8
    public TreeNode(int id, int val) {
9
      this.id = id;
10
      this.val = val;
11
      child = new ArrayList<>();
12
    }
13
  }
14

15
  public int[] getCoprimes(int[] nums, int[][] edges) {
16
    // making tree/graph with edges
17
    TreeNode[] tr = new TreeNode[nums.length];
18
    for (int i = 0; i < nums.length; i++) tr[i] = new TreeNode(i, nums[i]);
19
    for (int[] x : edges) {
20
      tr[x[0]].child.add(tr[x[1]]);
21
      tr[x[1]].child.add(tr[x[0]]);
22
    }
23
    // intializing answer array of length of tree's nodes which we will return
24
    int[] ans = new int[nums.length];
25
    Arrays.fill(ans, -1);
26
    // creating gcd to not compute gcd everytime
27
    boolean[][] gcd = new boolean[51][51];
28
    for (int i = 1; i <= 50; i++) {
29
      for (int j = i; j <= 50; j++) {
30
        if (find_gcd(i, j) == 1) {
31
          gcd[i][j] = true;
32
          gcd[j][i] = true;
33
        }
34
      }
35
    }
36
    int[][] latest = new int[51][2];
37
    // instead of latest[][] as 2d array we can also use 2 arrays, one for who is latest ancestor &
38
    // one for storing id
39
    // in [][0] we will store height of tree so latest ancestor will be called
40
    // in [][1] we will store id of latest tree
41
    // initializing all to -1
42
    for (int i = 0; i <= 50; i++) {
43
      latest[i][0] = -1;
44
      latest[i][1] = -1;
45
    }
46
    find_closest_ancestor(tr[0], new TreeNode(-1, -1), ans, latest, gcd, 0);
47
    return ans;
48
  }
49

50
  public void find_closest_ancestor(
51
      TreeNode root, TreeNode parent, int[] ans, int[][] latest, boolean[][] gcd, int height) {
52
    int val = root.val;
53
    int latest_id = 0;
54
    for (int i = 1; i <= 50; i++) {
55
      // if gcd [val][i] is true & latest[i][0] is latest ancestor i.e. it's height is more then
56
      // save that id
57
      if (gcd[val][i] && latest[latest_id][0] < latest[i][0]) latest_id = i;
58
    }
59
    ans[root.id] =
60
        latest[latest_id][1]; // even if no latest ancestor found latest[id][1] is -1 by default
61

62
    // this is must we will save before state & after calling all it's child we will make it as it
63
    // was before calling
64
    // like backtracking
65
    int pre_height = latest[val][0], pre_id = latest[val][1];
66
    latest[val][0] = height;
67
    latest[val][1] = root.id;
68

69
    // we recur with all child
70
    for (TreeNode root_child : root.child) {
71
      // we will check if we aren't going upward in tree so root.child!=parent then call function
72
      if (root_child != parent)
73
        find_closest_ancestor(root_child, root, ans, latest, gcd, height + 1);
74
    }
75
    // as it was before we will put it back
76
    latest[val][0] = pre_height;
77
    latest[val][1] = pre_id;
78
  }
79

80
  // simple gcd code
81
  public int find_gcd(int a, int b) {
82
    if (b == 0) return a;
83
    return find_gcd(b, a % b);
84
  }
85
}