推 oin1104: 大師 我看超久沒想到這解法 05/23 12:01
→ DJYOMIYAHINA: 我看答案的 對不起 05/23 12:03
→ DJYOMIYAHINA: 上次解這題的時候是看答案ㄉ 05/23 12:03
推 sustainer123: 大師 05/23 12:11
今天這題之前寫過
做一次operation，原本是指對edge的兩個node同時做xor with k
但其實可以把operation給轉換成: 對tree的任兩個node同時做xor with k
原因是當任兩個node有connect
只要對path上所有edge的端點node都做一次operation
就會等於對這任兩點做xor with k了
所以這題可以轉換成
對所有node做總共偶數次xor with k，能得到的最大sum是多少
用dp就可以結束惹
def maximumValueSum(self, nums, k, edges):
"""
:type nums: List[int]
:type k: int
:type edges: List[List[int]]
:rtype: int
"""
maximum_odd_cur = nums[0]^k
maximum_even_cur = nums[0]
for i in range(1, len(nums)):
maximum_odd_cur, maximum_even_cur = max(maximum_even_cur+(nums[i]^k),
maximum_odd_cur+nums[i]), max(maximum_odd_cur+(nums[i]^k), maximum_even_cur+
nums[i])
return maximum_even_cur
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.21.119.51 (日本)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1747972648.A.996.html
※ 編輯: DJYOMIYAHINA (1.21.119.51 日本), 05/23/2025 11:58:19