[Leetcode] 2322. Minimum Score After Removals on a Tree (i dont get)

https://leetcode.com/problems/minimum-score-after-removals-on-a-tree/?envType=daily-question&envId=2025-07-24

initial

It was similar to the programmers cutting edges question. So i got the general idea but the dfs way of calculating val^nums[neigh] was wrong. Look at my https://velog.io/@whitehousechef/DFS.

So my initial sol is correct but it causes TLE

class Solution:
    def minimumScore(self, nums: List[int], edges: List[List[int]]) -> int:
        ans=int(10e18)
        length = len(edges)
        n=len(nums)
        graph=[[] for _ in range(n)]
        connect=[[False for _ in range(n)] for _ in range(n)]
        for edge in edges:
            a,b=edge
            graph[a].append(b)
            graph[b].append(a)
            connect[a][b]=True
            connect[b][a]=True

        def dfs(node,visited_lst):
            nonlocal graph, connect,nums
            cur_val = nums[node]
            for neigh in graph[node]:
                if not visited_lst[neigh] and connect[node][neigh]:
                    visited_lst[neigh]=True
                    cur_val^=dfs(neigh,visited_lst)
            return cur_val

        for i in range(length):
            for j in range(i+1,length):
                lst=[]
                visited=[False for _ in range(n)]
                a,b=edges[i]
                c,d=edges[j]
                connect[a][b]=False
                connect[b][a]=False
                connect[c][d]=False
                connect[d][c]=False
                for k in range(n):
                    if not visited[k]:
                        visited[k]=True
                        val = dfs(k,visited)
                        lst.append(val)
                ans=min(ans, max(lst)-min(lst))
                connect[a][b]=True
                connect[b][a]=True
                connect[c][d]=True
                connect[d][c]=True

        return ans

sol (i dont get)

So we are doing dfs for each edge possibility, which causes TLE

class Solution:
    def minimumScore(self, nums: List[int], edges: List[List[int]]) -> int:
        n = len(nums)
        visited = [False for _ in range(n)]
        pc = []  # Store the parent-child edges from DFS tree
        adj = [[] for _ in range(n)]
        
        # Build adjacency list
        for edge in edges:
            adj[edge[0]].append(edge[1])
            adj[edge[1]].append(edge[0])
        
        # To store if node a contains b as one of its child in subtree
        childs = [[False for _ in range(n)] for _ in range(n)]
        
        # To store the XOR of node a and all its child subtree
        child_xor = [0 for _ in range(n)]
        
        # To store parents of current path during DFS
        par = []
        
        def dfs(i: int) -> int:
            ans = nums[i]
            visited[i] = True
            
            # Mark all ancestors that this node belongs to their subtree
            for p in par:
                childs[p][i] = True
            
            par.append(i)  # Add current node to parent path
            
            for child in adj[i]:
                if not visited[child]:
                    pc.append([i, child])  # Store parent-child edge
                    ans ^= dfs(child)
            
            par.pop()  # Remove current node from parent path
            child_xor[i] = ans
            return ans
        
        # Do single DFS to precompute everything
        dfs(0)
        
        ans = 1000000000
        
        # Try all pairs of parent-child edges
        for i in range(len(pc)):
            for j in range(i + 1, len(pc)):
                # Get the child nodes of the two edges we're removing
                a, b = pc[i][1], pc[j][1]
                
                # Calculate XOR values for the 3 components
                xa, xb, xc = child_xor[a], child_xor[b], child_xor[0]
                
                if childs[a][b]:  # a is an ancestor of b (b is in a's subtree)
                    xc ^= xa  # Remove a's subtree from total
                    xa ^= xb  # Remove b's subtree from a's subtree
                else:  # a and b are in different subtrees
                    xc ^= xa  # Remove a's subtree from total
                    xc ^= xb  # Remove b's subtree from total
                
                # Update minimum score
                ans = min(max(xa, xb, xc) - min(xa, xb, xc), ans)
        
        return ans

complexity

mine: n^3 time n^2 space
his: n^2 time and space