【数学归纳法】【位运算】【异或】3068最大节点价值之和

本文涉及知识点

数学归纳法 位运算 异或

LeetCode3068. 最大节点价值之和

给你一棵 n 个节点的 无向 树，节点从 0 到 n - 1 编号。树以长度为 n - 1 下标从 0 开始的二维整数数组 edges 的形式给你，其中 edges[i] = [ui, vi] 表示树中节点 ui 和 vi 之间有一条边。同时给你一个 正 整数 k 和一个长度为 n 下标从 0 开始的 非负 整数数组 nums ，其中 nums[i] 表示节点 i 的 价值 。
Alice 想 最大化 树中所有节点价值之和。为了实现这一目标，Alice 可以执行以下操作 任意 次（包括 0 次）：
选择连接节点 u 和 v 的边 [u, v] ，并将它们的值更新为：
nums[u] = nums[u] XOR k
nums[v] = nums[v] XOR k
请你返回 Alice 通过执行以上操作 任意次 后，可以得到所有节点 价值之和 的 最大值 。
示例 1：输入：nums = [1,2,1], k = 3, edges = [[0,1],[0,2]]
输出：6
解释：Alice 可以通过一次操作得到最大价值和 6 ：

  • 选择边 [0,2] 。nums[0] 和 nums[2] 都变为：1 XOR 3 = 2 ，数组 nums 变为：[1,2,1] -> [2,2,2] 。
    所有节点价值之和为 2 + 2 + 2 = 6 。
    6 是可以得到最大的价值之和。
    示例 2：

在这里插入图片描述

输入：nums = [2,3], k = 7, edges = [[0,1]]
输出：9
解释：Alice 可以通过一次操作得到最大和 9 ：

  • 选择边 [0,1] 。nums[0] 变为：2 XOR 7 = 5 ，nums[1] 变为：3 XOR 7 = 4 ，数组 nums 变为：[2,3] -> [5,4] 。
    所有节点价值之和为 5 + 4 = 9 。
    9 是可以得到最大的价值之和。
    示例 3：

在这里插入图片描述

输入：nums = [7,7,7,7,7,7], k = 3, edges = [[0,1],[0,2],[0,3],[0,4],[0,5]]
输出：42
解释：Alice 不需要执行任何操作，就可以得到最大价值之和 42 。

在这里插入图片描述

提示：

2 <= n == nums.length <= 2 * 104
1 <= k <= 109
0 <= nums[i] <= 109
edges.length == n - 1
edges[i].length == 2
0 <= edges[i][0], edges[i][1] <= n - 1
输入保证 edges 构成一棵合法的树。

位运算

x ⊕ k ⊕ k 的值是 x ，故对同一个节点操作 k 次后，结果不边。 x\oplus k \oplus k 的值是x，故对同一个节点操作k次后，结果不边。 x⊕k⊕k的值是x，故对同一个节点操作k次后，结果不边。

图论

树说明是连通的。树是无向连通无环图。

数学归纳法

一，节点a和b直接相连，根据题意，可以nums[a]和nums[b]分别 ⊕ \oplus ⊕ k。
二，节点a b 通过p条变相连，a 和c通过p+1条边相连，且最后一条边是bc。如果能nums[a]和nums[b]分别 ⊕ \oplus ⊕ k，其它节点不变。则可以nums[a]和nums[c] ⊕ \oplus ⊕ k,中间的节点不变。
分两步：
操作(a,b) 操作(b,c) ，由于nums[b] ⊕ \oplus ⊕ k 两次，其值不变。
也就是 任意连通的节点都可以 ⊕ \oplus ⊕ k，而不影响其它节点。

记录个节点 ⊕ \oplus ⊕k 的变化，如果变大的数量是偶数，全部变大；如果奇数，两种选择：
a,除最小的外，全部变大。
b,最小的减少最少的结合，余下的两两结合。

代码

class Solution {
public:
	long long maximumValueSum(vector<int>& nums, int k, vector<vector<int>>& edges) {
		vector<int> vAdd;
		for (const auto& n : nums) {
			vAdd.emplace_back((n ^ k) - n);
		}
		sort(vAdd.begin(), vAdd.end());
		long long llRet = std::accumulate(nums.begin(), nums.end(), 0LL);
		int index = std::upper_bound(vAdd.begin(), vAdd.end(), 0) - vAdd.begin();
		if (1 & (vAdd.size()-index)) {
			if ((index) && (vAdd[index] + vAdd[index - 1] >= 0)) {
				index--;
			}
			else {
				index++;
			}
		}
		llRet += std::accumulate(vAdd.begin()+ index, vAdd.end(), 0LL);
		return  llRet;
	}
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

测试用例

template<class T>
void Assert(const T& t1, const T& 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;
	int k;
	vector<vector<int>> edges;
	{
		Solution sln;
		nums = { 1, 2, 1 }, k = 3;
		auto res = sln.maximumValueSum(nums, k,edges);
		Assert(6LL, res);
	}
	{
		Solution sln;
		nums = { 2,3 }, k = 7;
		auto res = sln.maximumValueSum(nums, k, edges);
		Assert(9LL, res);
	}
	{
		Solution sln;
		nums = { 7,7,7,7,7,7 }, k = 3;
		auto res = sln.maximumValueSum(nums, k, edges);
		Assert(42LL, res);
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46

2024年3月版

class Solution {
public:
	long long maximumValueSum(vector<int>& nums, int k, vector<vector<int>>& edges) {
		vector<int> v;
		for (const auto& n : nums)
		{
			v.emplace_back((n ^ k) - n);
		}
		long long llRet = std::accumulate(nums.begin(), nums.end(), 0LL);
		sort(v.begin(), v.end());
		while (v.size() >= 2)
		{
			long long cur = v.back() + v[v.size() - 2];
			if (cur <= 0)
			{
				break;
			}
			llRet += cur;
			v.pop_back();
			v.pop_back();
		}
		return llRet;
	}
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步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++**实现。

文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树首页概览61211 人正在系统学习中
群中有博文配套源码
QQ群名片
注：本文转载自blog.csdn.net的闻缺陷则喜何志丹的文章"https://blog.csdn.net/he_zhidan/article/details/137791994"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！