1
class Solution {
2
 public:
3
  vector<int> adj[100009];
4
  vector<int> d[55];
5
  int dis[100009];
6
  void dfs(vector<int> &nums, vector<int> &ans, int i, int p, int h1) {
7
    int h = nums[i];
8
    dis[i] = h1;
9
    ans[i] = -1;
10
    int val = -1;
11
    for (int w = 1; w <= 50; w++) {
12
      if (__gcd(h, w) == 1) {
13
        if (d[w].size()) {
14
          int u = d[w].back();
15
          if (dis[u] > val) {
16
            val = dis[u];
17
            ans[i] = u;
18
          }
19
        }
20
      }
21
    }
22
    d[h].push_back(i);
23
    for (auto x : adj[i]) {
24
      if (x == p) continue;
25
      dfs(nums, ans, x, i, h1 + 1);
26
    }
27
    d[h].pop_back();
28
  }
29
  vector<int> getCoprimes(vector<int> &nums, vector<vector<int>> &edges) {
30
    int n = nums.size();
31
    for (int i = 0; i < n; i++) {
32
      adj[i].clear();
33
    }
34
    for (int i = 0; i < n - 1; i++) {
35
      adj[edges[i][0]].push_back(edges[i][1]);
36
      adj[edges[i][1]].push_back(edges[i][0]);
37
    }
38
    vector<int> ans(n);
39
    dfs(nums, ans, 0, -1, 0);
40
    return ans;
41
  }
42
};