1766. Tree of Coprimes Hard

1/**
2 * [1766] Tree of Coprimes
3 *
4 * There is a tree (i.e., 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.
5 * To represent this tree, you are given an integer array nums and a 2D array edges. Each nums[i] represents the i^th node's value, and each edges[j] = [uj, vj] represents an edge between nodes uj and vj in the tree.
6 * 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.
7 * 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.
8 * 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.
9 *  
10 * Example 1:
11 * <img alt="" src="https://assets.leetcode.com/uploads/2021/01/06/untitled-diagram.png" style="width: 191px; height: 281px;" />
12 * 
13 * Input: nums = [2,3,3,2], edges = [[0,1],[1,2],[1,3]]
14 * Output: [-1,0,0,1]
15 * Explanation: In the above figure, each node's value is in parentheses.
16 * - Node 0 has no coprime ancestors.
17 * - Node 1 has only one ancestor, node 0. Their values are coprime (gcd(2,3) == 1).
18 * - Node 2 has two ancestors, nodes 1 and 0. Node 1's value is not coprime (gcd(3,3) == 3), but node 0's
19 *   value is (gcd(2,3) == 1), so node 0 is the closest valid ancestor.
20 * - Node 3 has two ancestors, nodes 1 and 0. It is coprime with node 1 (gcd(3,2) == 1), so node 1 is its
21 *   closest valid ancestor.
22 * 
23 * Example 2:
24 * <img alt="" src="https://assets.leetcode.com/uploads/2021/01/06/untitled-diagram1.png" style="width: 441px; height: 291px;" />
25 * 
26 * Input: nums = [5,6,10,2,3,6,15], edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]]
27 * Output: [-1,0,-1,0,0,0,-1]
28 * 
29 *  
30 * Constraints:
31 * 
32 * 	nums.length == n
33 * 	1 <= nums[i] <= 50
34 * 	1 <= n <= 10^5
35 * 	edges.length == n - 1
36 * 	edges[j].length == 2
37 * 	0 <= uj, vj < n
38 * 	uj != vj
39 * 
40 */
41pub struct Solution {}
42
43// problem: https://leetcode.com/problems/tree-of-coprimes/
44// discuss: https://leetcode.com/problems/tree-of-coprimes/discuss/?currentPage=1&orderBy=most_votes&query=
45
46// submission codes start here
47
48impl Solution {
49    pub fn get_coprimes(nums: Vec<i32>, edges: Vec<Vec<i32>>) -> Vec<i32> {
50        vec![]
51    }
52}
53
54// submission codes end
55
56#[cfg(test)]
57mod tests {
58    use super::*;
59
60    #[test]
61    fn test_1766() {
62    }
63}
64