<p>There is an undirected connected tree with <code>n</code> nodes labeled from <code>0</code> to <code>n - 1</code> and <code>n - 1</code> edges.</p>

<p>You are given a <strong>0-indexed</strong> integer array <code>nums</code> of length <code>n</code> where <code>nums[i]</code> represents the value of the <code>i<sup>th</sup></code> node. You are also given a 2D integer array <code>edges</code> of length <code>n - 1</code> where <code>edges[i] = [a<sub>i</sub>, b<sub>i</sub>]</code> indicates that there is an edge between nodes <code>a<sub>i</sub></code> and <code>b<sub>i</sub></code> in the tree.</p>

<p>Remove two <strong>distinct</strong> edges of the tree to form three connected components. For a pair of removed edges, the following steps are defined:</p>

<ol>
	<li>Get the XOR of all the values of the nodes for <strong>each</strong> of the three components respectively.</li>
	<li>The <strong>difference</strong> between the <strong>largest</strong> XOR value and the <strong>smallest</strong> XOR value is the <strong>score</strong> of the pair.</li>
</ol>

<ul>
	<li>For example, say the three components have the node values: <code>[4,5,7]</code>, <code>[1,9]</code>, and <code>[3,3,3]</code>. The three XOR values are <code>4 ^ 5 ^ 7 = <u><strong>6</strong></u></code>, <code>1 ^ 9 = <u><strong>8</strong></u></code>, and <code>3 ^ 3 ^ 3 = <u><strong>3</strong></u></code>. The largest XOR value is <code>8</code> and the smallest XOR value is <code>3</code>. The score is then <code>8 - 3 = 5</code>.</li>
</ul>

<p>Return <em>the <strong>minimum</strong> score of any possible pair of edge removals on the given tree</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/05/03/ex1drawio.png" style="width: 193px; height: 190px;" />
<pre>
<strong>Input:</strong> nums = [1,5,5,4,11], edges = [[0,1],[1,2],[1,3],[3,4]]
<strong>Output:</strong> 9
<strong>Explanation:</strong> The diagram above shows a way to make a pair of removals.
- The 1<sup>st</sup> component has nodes [1,3,4] with values [5,4,11]. Its XOR value is 5 ^ 4 ^ 11 = 10.
- The 2<sup>nd</sup> component has node [0] with value [1]. Its XOR value is 1 = 1.
- The 3<sup>rd</sup> component has node [2] with value [5]. Its XOR value is 5 = 5.
The score is the difference between the largest and smallest XOR value which is 10 - 1 = 9.
It can be shown that no other pair of removals will obtain a smaller score than 9.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/05/03/ex2drawio.png" style="width: 287px; height: 150px;" />
<pre>
<strong>Input:</strong> nums = [5,5,2,4,4,2], edges = [[0,1],[1,2],[5,2],[4,3],[1,3]]
<strong>Output:</strong> 0
<strong>Explanation:</strong> The diagram above shows a way to make a pair of removals.
- The 1<sup>st</sup> component has nodes [3,4] with values [4,4]. Its XOR value is 4 ^ 4 = 0.
- The 2<sup>nd</sup> component has nodes [1,0] with values [5,5]. Its XOR value is 5 ^ 5 = 0.
- The 3<sup>rd</sup> component has nodes [2,5] with values [2,2]. Its XOR value is 2 ^ 2 = 0.
The score is the difference between the largest and smallest XOR value which is 0 - 0 = 0.
We cannot obtain a smaller score than 0.
</pre>

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

<ul>
	<li><code>n == nums.length</code></li>
	<li><code>3 &lt;= n &lt;= 1000</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>8</sup></code></li>
	<li><code>edges.length == n - 1</code></li>
	<li><code>edges[i].length == 2</code></li>
	<li><code>0 &lt;= a<sub>i</sub>, b<sub>i</sub> &lt; n</code></li>
	<li><code>a<sub>i</sub> != b<sub>i</sub></code></li>
	<li><code>edges</code> represents a valid tree.</li>
</ul>

class Solution:
    def minimumScore(self, nums: List[int], edges: List[List[int]]) -> int:

        def get_score(component1, component2, component3):
            all_components = [component1, component2, component3]
            all_components.sort()
            return all_components[2] - all_components[0]

        def mark_ancestor(src, par, root, graph, is_ancestor):
            is_ancestor[root][src] = True

            for i in graph[src]:
                if i == par:
                    continue
                mark_ancestor(i, src, root, graph, is_ancestor)

        def dfs(src, par, graph, val, subtree_xor, is_ancestor):
            subtree_xor[src] = val[src]
            mark_ancestor(src, par, src, graph, is_ancestor)

            for i in graph[src]:
                if i == par:
                    continue
                dfs(i, src, graph, val, subtree_xor, is_ancestor)
                subtree_xor[src] ^= subtree_xor[i]

        n = len(nums)
        graph = [[] for _ in range(n)]
        subtree_xor = [0] * n
        val = nums[:]
        is_ancestor = [[False] * n for _ in range(n)]

        # Build the graph
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        # Perform DFS to calculate subtree XORs and mark ancestors
        dfs(0, -1, graph, val, subtree_xor, is_ancestor)

        ans = float('inf')

        # Iterate over all pairs of nodes to calculate scores
        for c1 in range(1, n):
            for c2 in range(c1 + 1, n):
                if is_ancestor[c1][c2]:
                    comp1 = subtree_xor[c2]
                    comp2 = subtree_xor[c2] ^ subtree_xor[c1]
                    comp3 = subtree_xor[0] ^ comp1 ^ comp2
                    ans = min(ans, get_score(comp1, comp2, comp3))
                elif is_ancestor[c2][c1]:
                    comp1 = subtree_xor[c1]
                    comp2 = subtree_xor[c1] ^ subtree_xor[c2]
                    comp3 = subtree_xor[0] ^ comp1 ^ comp2
                    ans = min(ans, get_score(comp1, comp2, comp3))
                else:
                    comp1 = subtree_xor[c2]
                    comp2 = subtree_xor[c1]
                    comp3 = subtree_xor[0] ^ comp1 ^ comp2
                    ans = min(ans, get_score(comp1, comp2, comp3))

        return ans

#  *********************************************************************

        # Same using BFS

        n, m = len(N), len(E)
        
        G = collections.defaultdict(list)  # Graph
        C = collections.defaultdict(set)   # Children
        A = N[:]                  # subtree XOR value
        degree = [0] * n        # degree of each node 

        for x, y in E:
            G[x].append(y)
            G[y].append(x)
            degree[x] += 1
            degree[y] += 1
        
        V = 0   # XOR of all the nodes
        
        seen = set()
        dq = collections.deque()
        for i in range(n):
            V ^= N[i]
            if degree[i] == 1:
                dq.append(i)
                seen.add(i)
                
        # BFS, starting from the leaf nodes     
        while dq:
            cur = dq.popleft()
            for nxt in G[cur]:
                if nxt not in seen:  # 'nxt is not in seen' means that node 'nxt' is the parent of node 'cur'.
                    C[nxt].add(cur)   # Update node 'nxt''s children by adding all the children of 'cur' and 'cur' itself.
                    C[nxt] |= C[cur]
                    A[nxt] ^= A[cur]   # Update the XOR value of node 'nxt'
                degree[nxt] -= 1
                if degree[nxt] == 1:
                    seen.add(nxt)         # Only add a node into queue when it has no leaf nodes.
                    dq.append(nxt)
					
        ans = math.inf
        for i in range(m - 1):
            for j in range(i + 1, m):
                # Let a, c be the lower break points
                a, b = E[i]
                if b in C[a]: a, b = b, a 
                
                c, d = E[j]
                if d in C[c]: c, d = d, c
                
                # 3 cases: c is a's child, a is c's child, or a and b are two independent subtrees.
                if c in C[a]:
                    cur = [A[c], A[a]^A[c], V^A[a]]
                elif a in C[c]:
                    cur = [A[a], A[c]^A[a], V^A[c]]
                else:
                    cur = [A[a], A[c], V^A[a]^A[c]]
                ans = min(ans, max(cur) - min(cur))
            
        return ans


25400