搜索引擎竞价排名网站优化制作
- Leetcode 3068. Find the Maximum Sum of Node Values
- 1. 解题思路
- 2. 代码实现
- 题目链接：3068. Find the Maximum Sum of Node Values
1. 解题思路
这一题虽然标记为一道hard的题目，但其实就是一个脑筋急转弯的题目。
我们只需要想明白一点即可：
- 由于异或操作满足
x^y^y = x，对于一棵联通树，我们总可以通过有限次对相邻边地操作，使得任意两点(u, v)转变为(u^z, v^z)，而其他所有的节点都不发生变化。
因此，我们只需要计算出所有点如果进行异或操作之后可以得到的改变量，然后将其从大到小进行排序，两两配对之后考察最大能够获得多少累积增长即可。
2. 代码实现
给出python代码实现如下：
class Solution:def maximumValueSum(self, nums: List[int], k: int, edges: List[List[int]]) -> int:delta = sorted([(x ^ k) - x for i, x in enumerate(nums)], reverse=True)i, n = 0, len(delta)ans = sum(nums)while i+1 < n and delta[i] + delta[i+1] > 0:ans += delta[i] + delta[i+1]i += 2return ans
提交代码评测得到：耗时972ms，占用内存28MB。