本文涉及知识点
树 因子数 数论
LeetCode2440. 创建价值相同的连通块
有一棵 n 个节点的无向树，节点编号为 0 到 n - 1 。
给你一个长度为 n 下标从 0 开始的整数数组 nums ，其中 nums[i] 表示第 i 个节点的值。同时给你一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示节点 ai 与 bi 之间有一条边。
你可以 删除 一些边，将这棵树分成几个连通块。一个连通块的 价值 定义为这个连通块中 所有 节点 i 对应的 nums[i] 之和。
你需要删除一些边，删除后得到的各个连通块的价值都相等。请返回你可以删除的边数 最多 为多少。
示例 1：
输入：nums = [6,2,2,2,6], edges = [[0,1],[1,2],[1,3],[3,4]]
输出：2
解释：上图展示了我们可以删除边 [0,1] 和 [3,4] 。得到的连通块为 [0] ，[1,2,3] 和 [4] 。每个连通块的价值都为 6 。可以证明没有别的更好的删除方案存在了，所以答案为 2 。
示例 2：
输入：nums = [2], edges = []
输出：0
解释：没有任何边可以删除。
提示：
1 <= n <= 2 * 104
nums.length == n
1 <= nums[i] <= 50
edges.length == n - 1
edges[i].length == 2
0 <= edges[i][0], edges[i][1] <= n - 1
edges 表示一棵合法的树。
预备知识
下面是代码，性能可以优化：
auto vPrime = CreatePrime(1000'000); vector<int> cnts= { 0,1 }; for (int i = 2; i <= 1000'000; i++) { int cnt = 1; int tmp = i; for (const auto& p : vPrime) { int cnt1 = 1; while (0 == tmp % p) { cnt1++; tmp /= p; } cnt *= cnt1; if (1 == tmp) { break; } } cnts.emplace_back(cnt); } int iMaxIndex = std::max_element(cnts.begin(), cnts.end())- cnts.begin(); const int iMax = cnts[iMaxIndex];
深度优先搜索
sum是num之和。删除x条边，变成x+1个树，(x+1)如果不是sum的因子，则一定不符合题意。最多有240个符合题意的x。
故时间复杂度是：O(240n)。
对应每个x都要DFS判断是否符合题意。
num1 等于排除独立子树后本节点及子树节点的num和。如果num1等于sum/(x+1)，则返回0（独立，和父节点断开联系）。否则返回num1。
如果根节点返回0，则合法。否则非法。
以任意节点为根的结果一样，故以0为根。
num1等于sum/(x+1) 必须独立，因为不拆分的话，其祖先必定超过sum/(x+1)
代码
核心代码
class CNeiBo2 { public: CNeiBo2(int n, bool bDirect, int iBase = 0) :m_iN(n), m_bDirect(bDirect), m_iBase(iBase) { m_vNeiB.resize(n); } CNeiBo2(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0) :m_iN(n), m_bDirect(bDirect), m_iBase(iBase) { m_vNeiB.resize(n); for (const auto& v : edges) { m_vNeiB[v[0] - iBase].emplace_back(v[1] - iBase); if (!bDirect) { m_vNeiB[v[1] - iBase].emplace_back(v[0] - iBase); } } } inline void Add(int iNode1, int iNode2) { iNode1 -= m_iBase; iNode2 -= m_iBase; m_vNeiB[iNode1].emplace_back(iNode2); if (!m_bDirect) { m_vNeiB[iNode2].emplace_back(iNode1); } } const int m_iN; const bool m_bDirect; const int m_iBase; vector<vector<int>> m_vNeiB; }; class Solution { public: int componentValue(vector<int>& nums, vector<vector<int>>& edges) { const int sum = std::accumulate(nums.begin(), nums.end(), 0); CNeiBo2 neiBo(nums.size(), edges, false); for (int i = nums.size() - 1; i >= 1; i--) { if (0 == sum % (i + 1)) { if (0 == DFS(0, -1, neiBo.m_vNeiB, sum / (i + 1),nums)) { return i; } } } return 0; } int DFS(int cur, int par, vector<vector<int>>& neiBo, int value, const vector<int>& nums) { int sum1 = nums[cur]; for (const auto& next : neiBo[cur]) { if (next == par) { continue; } sum1 += DFS(next, cur, neiBo, value, nums); } //std::cout << cur << "->" << sum1 << std::endl; return (sum1 == value) ? 0 : sum1; } };
测试用例
template<class T,class T2> void Assert(const T& t1, const T2& t2) { assert(t1 == t2); } 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]); } } int main() { vector<int> nums; vector<vector<int>> edges; { Solution sln; nums = { 6,2,2,2,6 }, edges = { {0,1},{1,2},{1,3},{3,4} }; auto res = sln.componentValue(nums, edges); Assert(2, res); } { Solution sln; nums = { 2 }, edges = {}; auto res = sln.componentValue(nums, edges); Assert(0, res); } }
2023年7月
class Solution { public: int componentValue(vector& nums, vector<vector>& edges) { m_c = nums.size(); int iTotal = std::accumulate(nums.begin(), nums.end(), 0); CNeiBo2 neiBo(nums.size(), edges, false, 0); for (int iRegionNum = m_c; iRegionNum > 0; iRegionNum–) { if (0 != iTotal % iRegionNum) { continue; } const int regionSize = iTotal / iRegionNum; if (0 == DFS(0, -1, regionSize,nums, neiBo.m_vNeiB)) { return iRegionNum - 1; } } return 0; } int DFS(int cur, const int parent, const int size,const vector& nums, const vector<vector>& vNeiB) { int total = nums[cur]; for (const auto& next : vNeiB[cur]) { if (parent == next) { continue; } total += DFS(next, cur, size, nums, vNeiB); } return (size == total) ? 0 : total; } int m_c; };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步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++**实现。
