前天半夜打开看到hard就想说算了==
刚刚想了一下发现
反正是tree
好像可以不用管他怎么连了欸
写了一个完全没管edges的==
都先翻成大的加起来
如果翻的次数是奇数
就挑翻了影响最小的翻
nums走一圈
不过好像跑的有点慢
等等去看看别人都怎么写
class Solution {
public:
long long maximumValueSum(vector<int>& nums, int k, vector<vector<int>>& edges) {
long long n = nums.size();
long long flip = 0;
//long long minVal = LLONG_MAX;
long long res = 0;
long long diff = LLONG_MAX;
//vector <bool> flipBoard(n, false);
for(int i = 0; i < n; i++){
if( (nums[i] xor k) > nums[i] ){
flip++;
nums[i] = (nums[i] xor k);
}
cout << nums[i] << endl;
res += nums[i];
if(nums[i] - (nums[i] xor k) < diff){
diff = nums[i] - (nums[i] xor k);
}
}
if( (flip % 2) == 1){
res -= diff;
//cout << (minVal xor k);
}
return res;
}
};
※ 引述《JIWP (神楽めあ的钱包)》之铭言：
: 3068. Find the Maximum Sum of Node Values
: 一棵无向树有n个node
: nums[i]是第i个node的val
: edges[i]=[u,v]，代表u、v是相连的
: 给一个正整数k
: 你可以对同一条edge上的node进行以下操作
: edge[u,v]
: nums[u]=nums[u] XOR k
: nums[v]=nums[v] XOR k
: 请回传这些node经过任意次操作后的最大总和
: 思路 :
: 因为所有node都是相连的(不管是直接相连还是透过其他node相连)
: 可以直接对任意两点进行操作
: 所以题目就简化成对所有node进行偶数次操作后
: 找出最大的总和
: 用两个变量sumodd、sumeven分别表示经过奇数次、偶数次操作的最大值
: sumodd,sumeven=max(sumodd+nums[i],sumeven+nums[i]^k),max(sumeven+nums[i],sumod
: d+nums[i]^k)
: 最后回传sumeven
: golang code :
: func maximumValueSum(nums []int, k int, edges [][]int) int64 {
: sumodd,sumeven:=int64(nums[0]^k),int64(nums[0])
: for _,val:=range nums[1:]{
: sumodd,sumeven=max(sumodd+int64(val),sumeven+int64(val^k)),max(sumeven
: +int64(val),sumodd+int64(val^k))
: }
: return int64(sumeven)
: }
: func max(i,j int64)int64{
: if i>j{
: return i
: }
: return j
: }