Description

Submission

class Solution {
    vector<int> next[100000];
    int visited[100000];
    vector<int> rets;
    int n;
    vector<int> records[51]; // occurence of the number along the path
    vector<int> path;  // the t-th node id along the path

    void dfs(int cur, int depth, vector<int>& nums) {
        if(visited[cur]) return;
        visited[cur] = 1;
        
        // find the closest ancestor depth for the current node
        int d = -1; 
        for(int i = 1; i < 51; ++i) {
            if(records[i].size() > 0 && gcd(i, nums[cur]) == 1) {
                d = max(d, records[i].back());
            }
        }
        rets[cur] = (d == -1) ? -1 : path[d];

        // for the children
        path.push_back(cur);
        records[nums[cur]].push_back(depth);

        for(auto x: next[cur]) {
            if(visited[x]) continue;
            dfs(x, depth+1, nums);
        }

        records[nums[cur]].pop_back();
        path.pop_back();
    }


public:
    vector<int> getCoprimes(vector<int>& nums, vector<vector<int>>& edges) {
        n = nums.size();
        rets.resize(n);
        for(auto& e: edges) {
            next[e[0]].push_back(e[1]);
            next[e[1]].push_back(e[0]);
        }
        dfs(0, 0, nums);
        return rets;
    }
};