前天半夜打開看到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
: }