互质树

/*
 * Approach using Java Streams:
 * This problem is not particularly suited for Java Streams due to the complexity
 * and nature of DFS traversal and maintaining state during the traversal. Therefore,
 * a traditional approach with recursive DFS is more suitable here.
 */

import java.util.*;
import java.util.stream.*;

public class SolutionStream {
    private List<List<Integer>> tree;
    private int[] nums;
    private int[] result;

    public int[] getCoprimeAncestors(int[] nums, int[][] edges) {
        int n = nums.length;
        this.nums = nums;
        tree = IntStream.range(0, n).mapToObj(i -> new ArrayList<Integer>()).collect(Collectors.toList());
        Arrays.stream(edges).forEach(edge -> {
            tree.get(edge[0]).add(edge[1]);
            tree.get(edge[1]).add(edge[0]);
        });
        result = new int[n];
        Arrays.fill(result, -1);
        boolean[] visited = new boolean[n];
        dfs(0, -1, new HashMap<>(), visited);
        return result;
    }

    private void dfs(int node, int parent, Map<Integer, Integer> ancestors, boolean[] visited) {
        visited[node] = true;
        int nearestCoprimeAncestor = -1;
        for (int ancestor : ancestors.keySet()) {
            if (gcd(nums[node], nums[ancestor]) == 1) {
                if (nearestCoprimeAncestor == -1 || ancestors.get(nearestCoprimeAncestor) < ancestors.get(ancestor)) {
                    nearestCoprimeAncestor = ancestor;
                }
            }
        }
        result[node] = nearestCoprimeAncestor;
        int original = ancestors.getOrDefault(nums[node], -1);
        ancestors.put(nums[node], node);
        tree.get(node).stream().filter(neighbor -> !visited[neighbor]).forEach(neighbor -> dfs(neighbor, node, ancestors, visited));
        if (original == -1) {
            ancestors.remove(nums[node]);
        } else {
            ancestors.put(nums[node], original);
        }
    }

    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}