【树】【因子数】【数论】【深度优先搜索】2440. 创建价值相同的连通块

作者推荐

【二分查找】【C++算法】378. 有序矩阵中第 K 小的元素

本文涉及知识点

树 因子数 数论

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 * 10
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 表示一棵合法的树。

预备知识

任何整数 x 都可以表示为 a 1 n 1 a 2 n 2 ⋯ a m n m a i ( i ∈ [ 0 , m ] ) 是 x 的质因数 任何整数x都可以表示为a1^{n1}a2^{n2}\cdots am^{nm} ai(i\in[0,m])是x的质因数 任何整数x都可以表示为a1n1a2n2⋯amnmai(i∈[0,m])是x的质因数
所有的因数可以表示为： a 1 t 1 a 2 t 2 ⋯ a m t m , t i ∈ [ 0 , n t ] , i ∈ [ 0 , m ] 所有的因数可以表示为：a1^{t1}a2^{t2}\cdots am^{tm} , ti\in[0,nt] ,i\in[0,m] 所有的因数可以表示为：a1t1a2t2⋯amtm,ti∈[0,nt],i∈[0,m]
x ∈ [ 0 , 100 0 ′ 000 ] \in[0,1000'000] ∈[0,1000′000] 最大因子数为240，此时x为720720。
下面是代码，性能可以优化：

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++**实现。