本文涉及知识点
最大公约数 深度优先搜索
LeetCode1766. 互质树
给你一个 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
深度优先搜索
m_vLeve 记录所有节点的深度（层次）。m_vSta[x] 记录值为x的祖先节点，越近的祖先越靠近栈顶。
无论cur节点有多少祖先，我只需要考虑最多50个祖先。因为nums[cur] ∈ \in∈[1,50]。值相同的祖先，只需要考虑最近的，其它忽略。
代码
核心代码
class CNeiBo { public: static vector<vector<int>> Two(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0) { vector<vector<int>> vNeiBo(n); for (const auto& v : edges) { vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase); if (!bDirect) { vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase); } } return vNeiBo; } static vector<vector<std::pair<int, int>>> Three(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0) { vector<vector<std::pair<int, int>>> vNeiBo(n); for (const auto& v : edges) { vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase, v[2]); if (!bDirect) { vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase, v[2]); } } return vNeiBo; } static vector<vector<int>> Grid(int rCount, int cCount, std::function<bool(int, int)> funVilidCur, std::function<bool(int, int)> funVilidNext) { vector<vector<int>> vNeiBo(rCount * cCount); auto Move = [&](int preR, int preC, int r, int c) { if ((r < 0) || (r >= rCount)) { return; } if ((c < 0) || (c >= cCount)) { return; } if (funVilidCur(preR, preC) && funVilidNext(r, c)) { vNeiBo[cCount * preR + preC].emplace_back(r * cCount + c); } }; for (int r = 0; r < rCount; r++) { for (int c = 0; c < cCount; c++) { Move(r, c, r + 1, c); Move(r, c, r - 1, c); Move(r, c, r, c + 1); Move(r, c, r, c - 1); } } return vNeiBo; } static vector<vector<int>> Mat(vector<vector<int>>& neiBoMat) { vector<vector<int>> neiBo(neiBoMat.size()); for (int i = 0; i < neiBoMat.size(); i++) { for (int j = i + 1; j < neiBoMat.size(); j++) { if (neiBoMat[i][j]) { neiBo[i].emplace_back(j); neiBo[j].emplace_back(i); } } } return neiBo; } }; class Solution { public: vector<int> getCoprimes(vector<int>& nums, vector<vector<int>>& edges) { m_nums = nums; m_vLeve.resize(nums.size()); m_vRes.resize(nums.size()); auto neiBo = CNeiBo::Two(nums.size(),edges,false); DFS(neiBo, 0, -1); return m_vRes; } void DFS(vector<vector<int>>& neiBo, int cur, int par) { std::pair<int, int> leveNo = { -1,-1 }; for (int i = 1; i <= 50; i++) { if (m_vSta[i].empty()) { continue; } if (1 == gcd(m_nums[cur], i)) { leveNo = max(leveNo, { m_vLeve[m_vSta[i].top()],m_vSta[i].top() }); } } m_vRes[cur] = leveNo.second; if (-1 != par) { m_vLeve[cur] = m_vLeve[par] + 1; } m_vSta[m_nums[cur]].emplace(cur); for (const auto& next : neiBo[cur]) { if (next == par) { continue; } DFS(neiBo, next, cur); } m_vSta[m_nums[cur]].pop(); } stack<int> m_vSta[51]; vector<int> m_nums; vector<int> m_vLeve; vector<int> m_vRes; };
测试用例
template<class T> void Assert(const vector<T>& v1, const vector<T>& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { assert(v1[i] == v2[i]); } } template<class T> void Assert(const T& t1, const T& t2) { assert(t1 == t2); } int main() { vector<int> nums; vector<vector<int>> edges; { Solution slu; nums = { 2,3,3,2 }, edges = { {0,1},{1,2},{1,3} }; auto res = slu.getCoprimes(nums, edges); Assert({ -1,0,0,1 }, res); } { Solution slu; nums = { 5,6,10,2,3,6,15 }, edges = { {0,1},{0,2},{1,3},{1,4},{2,5},{2,6} }; auto res = slu.getCoprimes(nums, edges); Assert({ -1,0,-1,0,0,0,-1 }, res); } }
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 我想对大家说的话 |
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
