✅ [Python] BFS + Topological Sort w/ Explanation | Beats 100%
Python solution:\n\nclass Solution:\n    def componentValue(self, N:List[int], E: List[List[int]]) -> int:\n        total_sum, n = sum(nums), len(nums)\n       
Python solution:\n```\nclass Solution:\n    def componentValue(self, N:List[int], E: List[List[int]]) -> int:\n        total_sum, n = sum(nums), len(nums)\n        adj_list, dep_counts = collections.defaultdict(set), [0] * n\n        for v1, v2 in edges:\n            adj_list[v1].add(v2)\n            adj_list[v2].add(v1)\n            dep_counts[v1] += 1\n            dep_counts[v2] += 1\n\n        def can_partition_into_subtrees_with_sum_(target_tree_sum: int) -> bool:\n            v_subtree_sums, dep_counts_copy = nums[:], dep_counts[:]\n            v_dq = deque([i for i, dep_count in enumerate(dep_counts) if dep_count == 1])\n            while v_dq:\n                for _ in range(len(v_dq)):\n                    curr_v = v_dq.pop()\n                    if v_subtree_sums[curr_v] > target_tree_sum:\n                        return False\n                    elif dep_counts_copy[curr_v] == 0:  # can\'t come up with a short example to trigger this condition\n                        continue\n                    dep_counts_copy[curr_v] = 0\n                    for next_v in adj_list[curr_v]:\n                        if v_subtree_sums[curr_v] == target_tree_sum or dep_counts_copy[next_v] > 0:\n                            dep_counts_copy[next_v] -= 1\n                            if v_subtree_sums[curr_v] < target_tree_sum:\n                                v_subtree_sums[next_v] += v_subtree_sums[curr_v]\n                            if dep_counts_copy[next_v] == 0:\n                                return v_subtree_sums[next_v] == target_tree_sum\n                            elif dep_counts_copy[next_v] == 1:\n                                v_dq.appendleft(next_v)\n            return True\n\n        for possible_subtree_sum in range(total_sum // n, total_sum):\n            if total_sum % possible_subtree_sum == 0 and can_partition_into_subtrees_with_sum_(possible_subtree_sum):\n                return total_sum // possible_subtree_sum - 1\n        return 0\n```\nI put this together with help from https://leetcode.com/problems/create-components-with-same-value/discuss/2706736/Python-Explanation-with-pictures-BFS and cleaned it up to be easier for me to understand. (Would highly recommend checking out the pictures in the linked post).\n\nHere\'s the explanation I could come up with:\n1. **Only attempt to partition the tree into subtrees with a sum that is a perfect divisor of the total tree sum.**\nThe first thing to realize here (as the problem hint says), is that you can only split the tree into x subtrees if x cleanly divides the sum of nums.\n\t* Ex1: `nums = [1,2,1], sum(nums) = 4`. Here, it\'s obvious that we can\'t split the tree into 3 subtrees (which would be the optimal answer since we would be deleting all edges), because 4/3 is not an integer (ie 4 % 3 != 0)\n\t* Ex2: `nums = [6,8,10], sum(nums) = 24`. Here, it could be possible to split the tree into 3 subtrees with sum 8 since 24 % 3 == 0. In this case, now we need to actually run through the tree and see if we can successfully partition it into 3 subtrees of sum 8 (obviously not possible for the given example).\n\t* This principle provides the setup for the `for`-loop iterating from `[total_sum // n, total_sum)`. The minimum possible valid subtree sum would be `total_sum` split over n subtrees (ie 1-node trees), and the max would be a single tree with all nodes summing to `total_sum` (we don\'t need to manually check the max since it is the default answer if we can\'t do any splits).\n2. **Additional space required for performing the partitioning**\nTo perform the actual partition-checking, we define a function that takes in the required sum that each subtree must have, and attempts to split all the nodes into subtrees with that sum. In order for this function to do its job, it will need:\n\t*  An easy way to determine the neighbors of a given node.\n\t\t*   We build a standard adjacency list `adj_list` to do this.\n\t*  An easy way to track whether a given node has been used up or not.\n\t\t*  We build a dependency-count array `dep_counts` (aka the current "degree" of a vertex) to do this.\n\t*  An easy way to track the sum of the subtree at the current vertex being considered.\n\t\t*  We\'ll use the `nums` array for this.\n\t*  Since the partition function could be run multiple times for multiple possible subtree sums, and since we\'ll need to modify the subtree sums and `dep_counts` as we go, we\'ll need to make copies of these arrays each time the function executes. We\'ll use those copies during the function-execution.\n3. **Process the nodes in the tree starting from leaves first**\n\t* \tTo partition the tree into subtrees of sum x, we\'ll start from all the leaf nodes in the tree. The reason we want to start from leaf nodes rather than a middle node is that if a node has multiple neighbors to pick from, we don\'t know ahead-of-time which neighbor should be the correct one to pick such that other nodes in the tree will also be able to correctly form subtrees of sum x.\n\t* \tEx: Given this tree which you want to partition into subtrees of sum 3:\n\t\t```\n        1      2\n         \\    /\n          2--1\n         /    \\\n        3      3\n\t\t```\n\t\tIf you start at the first 2 with 3 neighbors, and you incorrectly pick the "1" to the right to make a subtree of sum 3, then the other nodes will not be able to form subtrees of sum 3. This would require some complex backtracking to undo, so it\'s better to start at the leaf nodes.\n\t* \t(In case you haven\'t already seen it...we\'re going to be running a topological sort lol) We\'ll build a deque of nodes `v_dq`, which will be instantiated with all nodes with `dep_count == 1` (ie leaves).\n4. **Perform the subtree-building in a topological-sort fashion**\nNow we\'ll just do a standard bfs-style iteration of the vertices in the deque which is common to topological sort problems. For all the elements in the deque, we pop off each one and do the following:\n\t* Let `curr_v` be the current vertex we are considering which we just popped off the deque\n\t* If the sum of the subtree at `curr_v` is > than the target sum, we know we\'ve failed the partitioning so we\'ll just return False immediately.\n\t\t* Ex: `nums=[10,2], sum(nums) = 12`, we\'d first try to partition the tree into 2 subtrees of sum 6. We check 10 and its sum is > 6, so we stop immediately.\n\t* Otherwise, if the dep_count of `curr_v` is 0, then we\'ll skip it and move on to the next vertex. I think this case only occurs if we added a vertex to a previous subtree while that vertex was sitting in the deque.\n\t\t* Ex: Unfortunately I can\'t come up with a simple example to demonstrate this. If you have one please let me know. (This condition is necessary to achieve fast runtime)\n\t* Otherwise we\'ll set the dep_count of `curr_v` to 0 to indicate that this node has been used up in a subtree that we\'re building. Now, for each of the neighbors of `curr_v` (denoted `next_v`), we do the following:\n\t\t* if the sum at `curr_v` is already equal to the target sum, then we know this tree is finished. Thus all neighboring nodes should no longer have a dependency on `curr_v` and we\'ll decrement their dep_count by 1. (Note this may cause the `dep_count` of some nodes to fall below 0 - this is not an issue because those nodes would have already been processed in our `v_dq` ahead-of-time due to having a lower dependency-count than us [this is the nature of a topological sort]).\n\t\t\t* if we find after decrementing the neighbor\'s `dep_count` that it\'s `dep_count == 0`, this indicates that we\'ve just processed all nodes in the tree (by the nature of a connected tree where the node with the most edges is processed last). So we\'ll just check whether our `tree_sum == target` and, if so, `return True` (else `return False`).\n\t\t\t* otherwise if the neighbor\'s `dep_count` is now 1, that means it\'s eligible to be processed in the next round of BFS, so we\'ll append it onto `v_dq`.\n\t\t* the only other possibility is that our `tree_sum` is < than the target sum (we already checked the > condition above so we would\'ve returned False by now). For this case, we can only consider neighbors whose `dep_count` is > 0 (otherwise we would end up looking at nodes that were already added to our subtree in the previous iteration).\n\t\t\t* Since we absolutely need another node in our subtree to potentially hit the target, we must add this neighbor into our subtree. (Remember that nodes in `v_dq` have only 1 dependency, which means there\'s only 1 option to pick for increasing our subtree sum.) Thus we will increment the `next_v` tree_sum value by `curr_v` tree_sum value.\n\t\t\t* Afterwards, the same logic as in the previous block applies:\n\t\t\t\t* if the neighbor we just added has `dep_count == 0`, it\'s the last node to be processed in the tree.\n\t\t\t\t* elif the neighbor\'s `dep_count == 1`, it\'s ready to be processed in the next round of BFS.\n\t\t\t\t* otherwise, the neighbor must have other dependencies that should be processed first before deciding if any more nodes should be added to our subtree that the neighbor is now in.\n\t* Note: There is a `return True` condition at the end of the function - this should not execute because our topological sort will handle it in the `if dep_counts_copy[next_v] == 0` condition.\n5. A nice thing to note about the final answer we return: If we are able to successfully partition the given tree into multiple subtrees, then the number of edges that were deleted is going to be exactly the `number of subtrees` - 1.\n\t* Ex: `nums=[8,8,8], sum(nums) = 24`. We can partition into 3 subtrees, which means we\'d remove 2 edges.\n\t\tSince all the nodes are connected in the beginning, to form 2 trees out of 1 tree, you delete one edge. Then to form 3 trees from 2 trees, you delete one more edge. etc.\n\t\t\nSorry if this was a little verbose. Hopefully it\'ll help me understand this if I look at it again a few years from now lol.
['Breadth-First Search', 'Topological Sort', 'Python']