<p>There exists an <strong>undirected</strong> tree with <code>n</code> nodes numbered <code>0</code> to <code>n - 1</code>. You are given a <strong>0-indexed</strong> 2D integer array <code>edges</code> of length <code>n - 1</code>, where <code>edges[i] = [u<sub>i</sub>, v<sub>i</sub>]</code> indicates that there is an edge between nodes <code>u<sub>i</sub></code> and <code>v<sub>i</sub></code> in the tree. You are also given a <strong>positive</strong> integer <code>k</code>, and a <strong>0-indexed</strong> array of <strong>non-negative</strong> integers <code>nums</code> of length <code>n</code>, where <code>nums[i]</code> represents the <strong>value</strong> of the node numbered <code>i</code>.</p>

<p>Alice wants the sum of values of tree nodes to be <strong>maximum</strong>, for which Alice can perform the following operation <strong>any</strong> number of times (<strong>including zero</strong>) on the tree:</p>

<ul>
	<li>Choose any edge <code>[u, v]</code> connecting the nodes <code>u</code> and <code>v</code>, and update their values as follows:

	<ul>
		<li><code>nums[u] = nums[u] XOR k</code></li>
		<li><code>nums[v] = nums[v] XOR k</code></li>
	</ul>
	</li>
</ul>

<p>Return <em>the <strong>maximum</strong> possible <strong>sum</strong> of the <strong>values</strong> Alice can achieve by performing the operation <strong>any</strong> number of times</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2023/11/09/screenshot-2023-11-10-012513.png" style="width: 300px; height: 277px;padding: 10px; background: #fff; border-radius: .5rem;" />
<pre>
<strong>Input:</strong> nums = [1,2,1], k = 3, edges = [[0,1],[0,2]]
<strong>Output:</strong> 6
<strong>Explanation:</strong> Alice can achieve the maximum sum of 6 using a single operation:
- Choose the edge [0,2]. nums[0] and nums[2] become: 1 XOR 3 = 2, and the array nums becomes: [1,2,1] -&gt; [2,2,2].
The total sum of values is 2 + 2 + 2 = 6.
It can be shown that 6 is the maximum achievable sum of values.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2024/01/09/screenshot-2024-01-09-220017.png" style="padding: 10px; background: rgb(255, 255, 255); border-radius: 0.5rem; width: 300px; height: 239px;" />
<pre>
<strong>Input:</strong> nums = [2,3], k = 7, edges = [[0,1]]
<strong>Output:</strong> 9
<strong>Explanation:</strong> Alice can achieve the maximum sum of 9 using a single operation:
- Choose the edge [0,1]. nums[0] becomes: 2 XOR 7 = 5 and nums[1] become: 3 XOR 7 = 4, and the array nums becomes: [2,3] -&gt; [5,4].
The total sum of values is 5 + 4 = 9.
It can be shown that 9 is the maximum achievable sum of values.
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2023/11/09/screenshot-2023-11-10-012641.png" style="width: 600px; height: 233px;padding: 10px; background: #fff; border-radius: .5rem;" />
<pre>
<strong>Input:</strong> nums = [7,7,7,7,7,7], k = 3, edges = [[0,1],[0,2],[0,3],[0,4],[0,5]]
<strong>Output:</strong> 42
<strong>Explanation:</strong> The maximum achievable sum is 42 which can be achieved by Alice performing no operations.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= n == nums.length &lt;= 2 * 10<sup>4</sup></code></li>
	<li><code>1 &lt;= k &lt;= 10<sup>9</sup></code></li>
	<li><code>0 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
	<li><code>edges.length == n - 1</code></li>
	<li><code>edges[i].length == 2</code></li>
	<li><code>0 &lt;= edges[i][0], edges[i][1] &lt;= n - 1</code></li>
	<li>The input is generated such that <code>edges</code> represent&nbsp;a valid tree.</li>
</ul>

from collections import deque

class Solution:
    def maximumValueSum(self, nums: List[int], k: int, edges: List[List[int]]) -> int:
        '''
        repeat as many times as you want:
        pick an edge (u,v)

        nums[u] = nums[u] XOR k
        nums[v] = nums[v] XOR k

        we want to maximize the sum of the entire tree

        k and nums[i] <= 10**9
        nums.length <= 10**4


        '''
        return self.solveDp2(nums, k, edges)
    
    def solveMath(self, nums, k, edges):
        '''
        n xor k may be larger or smaller than n
        but n xor k xor k is always equal to n

        we don't know ahead of time if n xor k will be larger or smaller, just need to try
        each flip results in an increase of

        ((u xor k) + (v xor k)) - (u + v))
        this can be negative, which means flipping decreased the total sum

        imagine example 1
        A - B - C
        possible combinations are
        xA - xB - C
        xA - B - xC
        A - xB - xC
        without an exhaustive search, how do we know which one is largest


        nodes form a tree - no cycles
        '''
        retur 
    
    def solveDp(self, nums, k, edges):
        '''
        let normal[v] be the maximum sum from leaf nodes to node v
            assuming v is in the "normal" state (nums[v])
        let flipped[v] be the maximum sum from leaf nodes to nove v
            assuming v is in the "flipped" state (nums[v] XOR k)
        
        for leaf nodes, 
            normal[v] = nums[v]
            flipped[v] = -math.inf, since leaf nodes cannot flip by themselves
        
        for non-leaf nodes
            normal[v] = nums[v] + 
                # each incoming edge/neighbor remains unchanged
                sum(max(normal[u], flipped[u])) for each (u,v) edge
            flipped[v] = nums[v] XOR 
                # flip each incoming edge/neighbor
                + sum(max(
                    normal[u] - nums[u] + nums[u] XOR k, # u was normal, flip it
                    flipped[u] - nums[u] XOR k + nums[u] # u was flipped, normal it
                ) for each (u,v) edge)
        
        starting a topological sort from leaf nodes,
        we should end up at exactly 1 node (the "root" node)
        the answer is max(normal[root], flipped[root])

        time: O(N)
        '''
        N = len(nums)
        adjList = [[] for n in range(N)]
        normal = [-math.inf for n in range(N)]
        flipped = [-math.inf for n in range(N)]
        leaves = set()

        for [u,v] in edges:
            adjList[u].append(v)
            adjList[v].append(u)

        seen = set()
        for u, neighbors in enumerate(adjList):
            if len(neighbors) == 1:
                # this node only has one outgoing edge, its a leaf
                leaves.add(u)

        
        q = deque(leaves)
        lastNode = None
        processed = set()
        while q:
            u = q.popleft()
            if u in processed:
                continue
            else:
                processed.add(u)
            # get all incoming edge/neighbors
            incoming = []
            for v in adjList[u]:
                if v in processed:
                    incoming.append(v)
                else:
                    q.append(v)
                    seen.add(v)
            '''
            24 (0)
            |
            1 (2) - 78 (1)
            |
            44 (4) - 97(3)

            24^6 = 30
            78^6 = 72
            
            for node 2, the best normal option is 1 + 24 + 78
            best flipped option is 1 + 30 + 72
            its possible to get a larger even sum
            even if each even flip is not optimal

            imagine a > a ^ c
            but b < b ^ c
            we dont know ahead of time if a + b < (a^c) + (b^c)
            but if we greedily only flip b, we assume a + b is larger
            
            we want to split and merge incoming into two sets, a and b
            bestEven[u] = max(
                bestEven(a) + bestEven(b),
                bestOdd(a) + bestOdd(b))
            bestOdd[u] = max(
                bestEven(a) + bestOdd(b),
                bestOdd(a) + bestEven(b)
            )
            where bestEven(s) returns the maximum sum of s with even number of flips
            and bestOdd does the opposite
            '''
            # return (bestEven, bestOdd)
            def organize(incoming):
                nonlocal flipped
                nonlocal normal
                nonlocal nums
                nonlocal k

                if not incoming:
                    # with nothing to organize, 
                    # best even is 0 and best odd is impossible
                    return 0, -math.inf
                elif len(incoming) == 1:
                    i = incoming[0]
                    bestEven = max(normal[i], flipped[i])
                    bestOdd = max(
                        normal[i] - nums[i] + (nums[i] ^ k),
                        flipped[i] - (nums[i] ^ k) + nums[i]
                    )
                    return bestEven, bestOdd
                else:
                    half = len(incoming)//2
                    lBestEven, lBestOdd = organize(incoming[:half])
                    rBestEven, rBestOdd = organize(incoming[half:])
                    bestEven = max(
                        lBestEven + rBestEven,
                        lBestOdd + rBestOdd
                    )
                    bestOdd = max(
                        lBestEven + rBestOdd,
                        lBestOdd + rBestEven
                    )
                    return bestEven, bestOdd

            # flipped[u] possible if number of incoming edge flips is odd
            # normal[u] possible if number of incoming edge flips is even
            print(f"node[{u}] has incoming nodes {incoming}")
            bestEven, bestOdd = organize(incoming)
            print(f"incoming {incoming} bestEven {bestEven} bestOdd {bestOdd}")
            normal[u] = nums[u] + bestEven
            flipped[u] = (nums[u] ^ k) + bestOdd

            print(f"normal[{u}] is {normal[u]}, flipped[{u}] is {flipped[u]}")
            print("\n")

        return max(normal[u], flipped[u])
    
    '''
    34/37 (4)
    |
    92/91 (1) - 3/4 (3) - 56/63 (6) - 56/63 (2)
    |
    0/7 (0)
    |
    23/17 (5)
    '''
    def solveDp2(self, nums, k, edges):
        '''
        previous attempt almost works, but bfs from all leaf nodes does not work
        because we are not guaranteed to converge on the same root node

        what if we just arbitrarily pick a leaf node as the root,
        set that as layer[0],
        set root.children as layer[1],
        and do a layer-by-layer iteration from bottom up
        '''
        N = len(nums)
        adjList = [[] for n in range(N)]
        normal = [-math.inf for n in range(N)]
        flipped = [-math.inf for n in range(N)]
        leaves = set()

        for [u,v] in edges:
            adjList[u].append(v)
            adjList[v].append(u)

        for u, neighbors in enumerate(adjList):
            if len(neighbors) == 1:
                # this node only has one outgoing edge, set it as root
                root = u
                break
        
        parent = [None for _ in range(N)]
        children = [[] for _ in range(N)]
        q = deque([root])
        order = []
        while q:
            u = q.popleft()
            order.append(u)
            # u -> v
            for v in adjList[u]:
                if v != parent[u]:
                    children[u].append(v)
                    parent[v] = u
                    q.append(v)

        normal = [-math.inf for n in range(N)]
        flipped = [-math.inf for n in range(N)]        

        def organize(incoming):
                nonlocal flipped
                nonlocal normal
                nonlocal nums
                nonlocal k

                if not incoming:
                    # with nothing to organize, 
                    # best even is 0 and best odd is impossible
                    return 0, -math.inf
                elif len(incoming) == 1:
                    i = incoming[0]
                    bestEven = max(normal[i], flipped[i])
                    bestOdd = max(
                        normal[i] - nums[i] + (nums[i] ^ k),
                        flipped[i] - (nums[i] ^ k) + nums[i]
                    )
                    return bestEven, bestOdd
                else:
                    half = len(incoming)//2
                    lBestEven, lBestOdd = organize(incoming[:half])
                    rBestEven, rBestOdd = organize(incoming[half:])
                    bestEven = max(
                        lBestEven + rBestEven,
                        lBestOdd + rBestOdd
                    )
                    bestOdd = max(
                        lBestEven + rBestOdd,
                        lBestOdd + rBestEven
                    )
                    return bestEven, bestOdd

        # maximize sum by reverse order
        for u in reversed(order):
            #print(f"node[{u}] has incoming nodes {children[u]}")
            bestEven, bestOdd = organize(children[u])
            #print(f"incoming {children[u]} bestEven {bestEven} bestOdd {bestOdd}")
            normal[u] = nums[u] + bestEven
            flipped[u] = (nums[u] ^ k) + bestOdd

            #print(f"normal[{u}] is {normal[u]}, flipped[{u}] is {flipped[u]}\n")

        return max(normal[root], flipped[root])
        
31000