[Python] Top-Down DP, O(n^5). 35 ms and faster than 100%, explained
Idea\n\nI didn\'t see any posted DP solutions with a full writeup (or decent comments), so I wrote out each step in detail. The idea here is to choose any verte
**Idea**\n\nI didn\'t see any posted DP solutions with a full writeup (or decent comments), so I wrote out each step in detail. The idea here is to choose any vertex `x` with neighbors `v1,v2...,vk`, and pretend that we have removed each edge `x--vi`. Suppose we only remove the first edge, `x--v1`, to split our tree T into two smaller trees Tx and Tv1 rooted at x and v1. **If we compute diameters and counts for subtrees in `Tx` and `Tv1`, we can \'merge\' these** (i.e. add back the edge `v1`) to find diameters and counts for a combined tree rooted at `x`. We do this merging once for each neighbor, adding back the edge to `v1`, then to `v2` and so on.\n\n**Complexity**\n\nTime: `O(n^5)` We call merge exactly once for each edge; merge is called only from compute_subtree_counts, and compute_subtree_counts is called exactly once for each vertex. There are, worst case, `O(n^4)` operations in merge. Our outer loop in merge is over all (diameter, height) pairs of each subtree of `parent_vertex`, which can be at most `O(n^2)`; the inner loop is also at most `O(n^2)`. In practice, the time complexity is much better than `O(n^5)`, so perhaps it\'s possible to prove a smaller upper bound.\n\nThere may be a way to get `O(n^2)` or `O(n^3)` by using bottom-up DP and precomputing sums in the merge function [as discussed in this post](https://leetcode.com/problems/count-subtrees-with-max-distance-between-cities/discuss/896313/O(n2)-using-DP). If you find an implementation (or even detailed pseudocode) of that idea, please let me know. Space complexity is `O(n^3)` worst case, but I suspect this can be brought down to `O(n^2)` (and I suspect the true value of the current code to already be `O((n^2) log n)`) .\n\n\n**Python**\n\n\n```python\nclass Solution:\n    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n        # Create Tree as adjacency list\n        neigh: List[List[int]] = [[] for _ in range(n)]\n        for u, v in edges:\n            neigh[u - 1].append(v - 1)\n            neigh[v - 1].append(u - 1)\n\n        distance_array: List[int] = [0] * n\n\n        def find_tree_center(vertices: List[int], adj_list: List[List[int]]) -> int:\n            """Given a tree, return a central vertex (minimum radius vertex) with BFS"""\n\n            num_neighbors: List[int] = list(map(len, adj_list))\n            leaf_nodes: Deque[int] = collections.deque((x for x in range(len(vertices)) if num_neighbors[x] == 1))\n            while len(leaf_nodes) > 1:\n                leaf = leaf_nodes.popleft()\n                for neighbor in adj_list[leaf]:\n                    num_neighbors[neighbor] -= 1\n                    if num_neighbors[neighbor] == 1:\n                        leaf_nodes.append(neighbor)\n            return leaf_nodes[0]\n\n        def merge_into_parent(parent_subtrees: Dict[Tuple[int, int], int],\n                              child_subtrees: Dict[Tuple[int, int], int]) -> None:\n\n            """ Helper function to merge two disjoint rooted trees T_parent and T_child rooted at \'parent\' and \'child\',\n               into one tree rooted at \'parent\', by adding an edge from \'parent\' to \'child\'.\n               Called once for each edge in our tree. parent_subtrees[i, j] is the count of rooted subtrees\n               of T_parent that contain \'parent\', have diameter i, and height j.\n               Worst case complexity: O(n^4) per call\n            """\n\n            for (diam_for_parent, height_for_parent), count_from_parent in list(parent_subtrees.items()):\n\n                for (diam_for_child, height_for_child), count_from_child in child_subtrees.items():\n\n                    new_diameter = max(diam_for_parent, diam_for_child, height_for_parent + height_for_child + 1)\n                    new_height = max(height_for_parent, height_for_child + 1)\n                    parent_subtrees[new_diameter, new_height] = parent_subtrees.get((new_diameter, new_height), 0) + count_from_child * count_from_parent\n\n            return None\n\n        def compute_subtree_counts(current_vertex: int,\n                                   last_vertex: int = -1) -> Dict[Tuple[int, int], int]:\n            """Recursively counts subtrees rooted at current_vertex using DFS,\n            with edge from current_vertex to \'last_vertex\' (parent node) cut off"""\n            subtree_counts: Dict[Tuple[int, int], int] = {(0, 0): 1}\n\n            for child_vertex in neigh[current_vertex]:\n                if child_vertex == last_vertex:\n                    continue\n\n                merge_into_parent(parent_subtrees=subtree_counts,\n                                  child_subtrees=compute_subtree_counts(current_vertex=child_vertex,\n                                                                        last_vertex=current_vertex))\n\n            for (diameter, height), subtree_count in subtree_counts.items():\n                distance_array[diameter] += subtree_count\n\n            return subtree_counts\n\n        # Optimization: Use a max-degree vertex as our root to minimize recursion depth\n        max_degree_vertex: int = find_tree_center(vertices=list(range(n)),\n                                                  adj_list=neigh)\n\n        compute_subtree_counts(current_vertex=max_degree_vertex)\n\n        return distance_array[1:]\n```
['Dynamic Programming', 'Python3']