1766. Tree of Coprimes¶
题目信息¶
- 题号:
1766
- 难度:
Hard
- 主题:
树、深度优先搜索、最大公约数
- 原题:
- 重点:
对每个节点寻找路径上最近且节点值与其互质的严格祖先
题目重述¶
树根为节点 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]
解释:根节点没有祖先。