互质树

标签: 树 深度优先搜索 广度优先搜索 数学

难度: Hard

给你一个 n 个节点的树（也就是一个无环连通无向图），节点编号从 0 到 n - 1 ，且恰好有 n - 1 条边，每个节点有一个值。树的 根节点 为 0 号点。

给你一个整数数组 nums 和一个二维数组 edges 来表示这棵树。nums[i] 表示第 i 个点的值，edges[j] = [uj, vj] 表示节点 uj 和节点 vj 在树中有一条边。

当 gcd(x, y) == 1 ，我们称两个数 x 和 y 是 互质的 ，其中 gcd(x, y) 是 x 和 y 的 最大公约数 。

从节点 i 到 根 最短路径上的点都是节点 i 的祖先节点。一个节点 不是 它自己的祖先节点。

请你返回一个大小为 n 的数组 ans ，其中 ans[i]是离节点 i 最近的祖先节点且满足 nums[i] 和 nums[ans[i]] 是 互质的 ，如果不存在这样的祖先节点，ans[i] 为 -1 。

 

示例 1：

输入：nums = [2,3,3,2], edges = [[0,1],[1,2],[1,3]]
输出：[-1,0,0,1]
解释：上图中，每个节点的值在括号中表示。
- 节点 0 没有互质祖先。
- 节点 1 只有一个祖先节点 0 。它们的值是互质的（gcd(2,3) == 1）。
- 节点 2 有两个祖先节点，分别是节点 1 和节点 0 。节点 1 的值与它的值不是互质的（gcd(3,3) == 3）但节点 0 的值是互质的(gcd(2,3) == 1)，所以节点 0 是最近的符合要求的祖先节点。
- 节点 3 有两个祖先节点，分别是节点 1 和节点 0 。它与节点 1 互质（gcd(3,2) == 1），所以节点 1 是离它最近的符合要求的祖先节点。

示例 2：

输入：nums = [5,6,10,2,3,6,15], edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]]
输出：[-1,0,-1,0,0,0,-1]

 

提示：

  • nums.length == n
  • 1 <= nums[i] <= 50
  • 1 <= n <= 105
  • edges.length == n - 1
  • edges[j].length == 2
  • 0 <= uj, vj < n
  • uj != vj

Submission

运行时间: 432 ms

内存: 71.9 MB

class Solution:
    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:
        n=len(nums)
        g=[[] for _ in range(n)]
        for i,j in edges:
            g[i].append(j)
            g[j].append(i)
        d=defaultdict(set)
        arr=list(set(nums))
        nn=len(arr)
        for i in range(nn):
            for j in range(i,nn):
                if gcd(arr[i],arr[j])==1:
                    d[arr[i]].add(arr[j])
                    d[arr[j]].add(arr[i])
        ans=[-1]*n
        temp=defaultdict(int)
        def dfs(x,fa,res):
            if nums[x] in res:
                ans[x]=res[nums[x]]
            res2=res.copy()
            for i in d[nums[x]]:
                res2[i]=x
            for i in g[x]:
                if i!=fa:
                    dfs(i,x,res2)
        dfs(0,0,temp)
        return ans

Explain

此题解的思路是首先构建无向图的邻接表表示树结构。然后通过预处理找出所有数对之间是否互质，构建一个互质关系的字典。使用深度优先搜索（DFS）遍历树，同时维护每个数值最近的祖先节点信息。在DFS过程中，对每个节点检查其值与其所有可能的互质数的最近祖先节点，更新结果数组。这种方法避免了在DFS遍历中对每个节点重新计算gcd，从而优化了性能。

时间复杂度: O(n)

空间复杂度: O(n)

python
class Solution:
    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:
        n = len(nums)
        g = [[] for _ in range(n)]  # 邻接表表示图的结构
        for i, j in edges:
            g[i].append(j)
            g[j].append(i)

        d = defaultdict(set)  # 存储互质关系
        arr = list(set(nums))
        nn = len(arr)
        for i in range(nn):  # 预处理互质关系
            for j in range(i, nn):
                if gcd(arr[i], arr[j]) == 1:
                    d[arr[i]].add(arr[j])
                    d[arr[j]].add(arr[i])

        ans = [-1] * n  # 结果数组
        temp = defaultdict(int)  # 祖先节点信息

        def dfs(x, fa, res):
            if nums[x] in res:
                ans[x] = res[nums[x]]  # 更新结果
            res2 = res.copy()  # 拷贝当前的祖先节点信息
            for i in d[nums[x]]:
                res2[i] = x  # 更新祖先节点信息
            for i in g[x]:
                if i != fa:
                    dfs(i, x, res2)  # 递归遍历子节点

        dfs(0, 0, temp)  # 从根节点开始DFS
        return ans

Explore

为了高效预处理所有数对之间的互质关系，首先从输入的`nums`数组中提取所有唯一的数值，存入数组`arr`。然后对`arr`中的每一对元素(i, j)计算它们的最大公约数（gcd）。如果gcd为1，则认为这两个数是互质的，将它们互相加入到互质关系的字典`d`中。这样，通过只比较不同的数值，可以确保覆盖所有必要的情况而不重复计算，从而提高效率。预处理过程中，使用双层循环遍历`arr`中的每个元素，外层循环元素为i，内层循环元素为j，从i开始，这样可以避免重复检查并减少计算量。

`res`参数在DFS函数中用于存储和跟踪当前递归路径上各个数值的最近祖先节点的索引。在DFS遍历过程中，每当遍历到一个新节点x时，会检查`nums[x]`在`res`中是否已有记录，如果有，则将对应的祖先节点索引更新到结果数组`ans`中。此外，每次递归调用之前，会复制`res`到`res2`，然后更新`res2`以包含当前节点x的信息。这样，每个递归层级都有其对应的祖先信息，确保了信息的正确传递和更新。

在DFS中，使用`res2 = res.copy()`进行深拷贝是必要的，因为这样可以确保在递归过程中对祖先信息的更新不会影响其他递归分支的祖先信息。如果直接使用`res`而不进行拷贝，那么在递归过程中对`res`的修改将影响到所有使用`res`的递归分支，这将导致错误的祖先信息传递。通过深拷贝，每个递归调用都维护了一个独立的祖先信息状态，从而确保了每个节点的处理是正确和独立的。

题解中提到的数字50并未直接提及其来源，因此这可能是基于对题目数据范围的理解或假设。例如，如果输入的数值范围限制在1到50之间，那么理论上最多可能有50个不同的数值需要跟踪其最近的祖先节点。因此，每次DFS调用更新的祖先节点信息数量取决于这些数值的范围和特性。如果题目或输入数据确实限制了数值范围或类型，那么这个数字就与输入数据的这些属性有关。