→ DJYOSHITAKA: 別捲了 05/19 12:23
→ Rushia: 你好優秀 05/19 23:44
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
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.71.215.173 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1716091331.A.5E6.html