Readme

1766.Tree-of-Coprimes

本题本质就是DFS。当我们考察某个节点curIdx时，在该DFS路径path上的所有节点都是它的祖先。我们需要从中找一个深度最大的、与nums[curIdx]互质的节点。理论上我们需要逆序遍历一遍path，总体复杂度是o(N^2)。

本题特殊之处在于数据范围限制了所有节点的“数值”不超过50，于是我们可以不遍历节点、转而遍历“数值”来更高效的找到互质的节点。我们只需要在维护path的同时，维护一个哈希表records，其中records[d]存储的就是path里所有数值是d的节点的深度。我们在1到50里面寻找那些与nums[curIdx]互质的d，其中最大的records[d].back()就是离curIdx最近的互质节点的深度。再根据这个深度，直接从path里面读取那个节点的idx。