1766.互质树

链接：1766.互质树
难度：Hard
标签：树、深度优先搜索、数组、数学、数论
简介：请你返回一个大小为 n 的数组 ans ，其中 ans[i]是离节点 i 最近的祖先节点且满足 nums[i] 和 nums[ans[i]] 是 互质的 ，如果不存在这样的祖先节点，ans[i] 为 -1 。

题解 1 - python

• 编辑时间：2024-04-11
• 执行用时：1017ms
• 内存消耗：66.86MB
• 编程语言：python
• 解法介绍：预处理后dfs。

primes = [0 for _ in range(51)]
    for num1 in range(1, 51):
        for num2 in range(1, 51):
            if gcd(num1, num2) == 1:
                primes[num1] |= 1 << num2
                primes[num2] |= 1 << num1
    
    class Solution:
        def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:
            n = len(nums)
            nodes = [[] for _ in range(n)]
            for n1, n2 in edges:
                nodes[n1].append(n2)
                nodes[n2].append(n1)
            ans = [-1 for _ in range(n)]
            def dfs(node: int, arr: List[Tuple[int, int]], parent: int, level: int):
                num1 = nums[node]
                cur = (-1, -1)
                for num2 in range(1, 51):
                    if arr[num2][0] != -1 and primes[num1] & (1 << num2) and (cur[1] == -1 or arr[num2][1] > cur[1]):
                        cur = arr[num2]
                ans[node] = cur[0]
                oldv = arr[num1]
                arr[num1] = (node, level)
                for child in nodes[node]:
                    if child != parent:
                        dfs(child, arr, node, level + 1)
                arr[num1] = oldv
            dfs(0, [(-1, -1) for _ in range(51)], -1, 0)
            return ans