Step-by-step breakdown
Approach\nAccepted brute force using:\n- Backtracking to find all subset graphs\n- BFS to check if the subset graph is connected and find the farthest leaf node
# Approach\nAccepted brute force using:\n- Backtracking to find all subset graphs\n- BFS to check if the subset graph is connected and find the farthest leaf node\n- If it is connected then it is subtree as per the rule\n- DFS for finding the largest distance between any two nodes (in other words, farthest distance from the found leaf node)\n- Ultimately, increase the subtree count (initiated with zero) for the distance\n\n# Complexity\n- Time complexity:\n`O(2^n . n)`\n\n- Space complexity:\n`O(n)`\n\n# Code\n```python3 []\nclass Solution:\n    def maximumSubtreeDistance(self, adj_list, node, parent, subtree):\n        dist = 0\n        for nbr in adj_list[node]:\n            if parent != nbr and nbr in subtree:\n                dist = max(dist, self.maximumSubtreeDistance(adj_list, nbr, node, subtree))\n        if node == parent:\n            return dist\n        return dist + 1\n    \n    def checkValidSubtreeAndFarthestNode(self, subtree, adj_list, first_node):\n        if len(subtree) == 0:\n            return False\n        visited = {node: False for node in subtree}\n        dist = 0\n        q = deque([(dist, first_node)])\n        visited[first_node] = True\n        farthest_node = first_node\n        max_dist = 0\n        while len(q) > 0:\n            dist, node = q.popleft()\n            if max_dist < dist:\n                farthest_node = node\n                max_dist = dist\n            for nbr in adj_list[node]:\n                if nbr in subtree and visited[nbr] is False:\n                    q.append((dist + 1, nbr))\n                    visited[nbr] = True\n        return all(visited.values()), farthest_node\n    \n    def countSubtrees(self, adj_list, subtree, node, subtree_count):\n        if node == len(adj_list):\n            if len(subtree) == 0:\n                return\n            start_node = list(subtree)[0]\n            valid_subtree, farthest_node = self.checkValidSubtreeAndFarthestNode(subtree, adj_list, start_node)\n            if valid_subtree:\n                dist = self.maximumSubtreeDistance(adj_list, farthest_node, farthest_node, subtree)\n                subtree_count[dist] = subtree_count.get(dist, 0) + 1\n            return\n        self.countSubtrees(adj_list, subtree, node + 1, subtree_count)\n        self.countSubtrees(adj_list, set(list(subtree) + [node]), node + 1, subtree_count)\n    \n    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n        subtree_count = {}\n        subtree = set()\n        adj_list = {node: [] for node in range(n)}\n        for (u, v) in edges:\n            node, nbr = u-1, v-1\n            adj_list[node].append(nbr)\n            adj_list[nbr].append(node)\n        start_node = 0\n        self.countSubtrees(adj_list, subtree, start_node, subtree_count)\n        ans = []\n        no_subtree_cnt = 0\n        for d in range(1, n):\n            ans.append(subtree_count.get(d, no_subtree_cnt))\n        return ans\n```
['Graph', 'Python3']