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],sumodd+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
}