本文涉及知识点

数学归纳法 位运算 异或

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 * 10⁴
1 <= k <= 10⁹
0 <= nums[i] <= 10⁹
edges.length == n - 1
edges[i].length == 2
0 <= edges[i][0], edges[i][1] <= n - 1
输入保证 edges 构成一棵合法的树。

位运算

$$x\oplus k\oplus 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;}
};

测试用例

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);}
}

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;}
};

扩展阅读

视频课程

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