Cut The Tree Hackerrank Solution Python Apr 2026

def cutTheTree(n, edges, values): # Build adjacency list adj = [[] for _ in range(n + 1)] for u, v in edges: adj[u].append(v) adj[v].append(u) # Calculate total sum of all node values total_sum = sum(values) # Store subtree sums subtree_sum = [0] * (n + 1) visited = [False] * (n + 1) # DFS to calculate subtree sums def dfs(node): visited[node] = True subtree_sum[node] = values[node - 1] # values are 0-indexed for neighbor in adj[node]: if not visited[neighbor]: dfs(neighbor) subtree_sum[node] += subtree_sum[neighbor] # Start DFS from node 1 (root) dfs(1) # Find minimum difference min_diff = float('inf') for i in range(2, n + 1): # Start from 2 because cutting edge from root would give diff = total_sum diff = abs(total_sum - 2 * subtree_sum[i]) if diff < min_diff: min_diff = diff return min_diff