本文涉及知识点
数学归纳法 位运算 异或
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 构成一棵合法的树。
位运算
图论
树说明是连通的。树是无向连通无环图。
数学归纳法
一，节点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; } };
| 我想对大家说的话 |
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
