1766. Tree of Coprimes

题目信息

题号:

1766

难度:

Hard

主题:

树、深度优先搜索、最大公约数

原题:

LeetCode 1766

重点:

对每个节点寻找路径上最近且节点值与其互质的严格祖先

题目重述

树根为节点 0。返回数组 ans,其中 ans[i] 是与 nums[i] 互质的最近祖先编号;不存在时为 -1。

自建示例

输入:nums = [2,3,3], edges = [[0,1],[1,2]]
输出:[-1,0,0]
解释:节点 2 与父节点值 3 不互质,但与根节点值 2 互质。
输入:nums = [7], edges = []
输出:[-1]
解释:根节点没有祖先。