BFS + tree DP
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \nuse BFS\n1) add each si
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nuse BFS\n1) add each single node into the queue\n2) each step , extend one more node to get a new tree\n3) for each tree, use DP with tree to get the max distance\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n        lookup = [[] for _ in range(n+1)]\n        for u, v in edges:\n            lookup[u].append(v)\n            lookup[v].append(u)\n\n        def get_max_distance(tree):\n            root = 0\n            for i in range(1, n+1):\n                if (1 << i) & tree:\n                    root = i\n                    break\n            distance = 0\n            fathers = set([root])\n            def dp(node): # get max path length ending with this node\n                nonlocal distance\n                childs = []\n                for next in lookup[node]:\n                    if (1 << next) & tree:\n                        if next in fathers:\n                            continue\n                        fathers.add(next)\n                        childs.append(dp(next))\n                if len(childs) == 0:\n                    return 0\n                if len(childs) == 1:\n                    distance = max(distance, childs[0] + 1)\n                    return childs[0] + 1\n                \n                childs.sort()\n                # get max path pass through this node\n                distance = max(distance, childs[-1] + childs[-2] + 2)\n                return childs[-1] + 1\n\n            dp(root)\n            return distance\n        \n        q = deque()\n        visited = set()\n        for i in range(1, n+1):\n            q.append(1 << i)\n            visited.add(1 << i)\n        res = [0 for _ in range(n - 1)]\n        while q:\n            cur = q.popleft()\n            if cur.bit_count() > 1:\n                res[get_max_distance(cur)-1] += 1\n\n            for u, v in edges:\n                uin, vin = (1 << u) & cur, (1 << v) & cur\n                if uin and vin:\n                    continue\n                if (not uin) and (not vin):\n                    continue\n                if uin:\n                    next = cur | (1 << v)\n                    if next not in visited:\n                        visited.add(next)\n                        q.append(next)\n                elif vin:\n                    next = cur | (1 << u)\n                    if next not in visited:\n                        visited.add(next)\n                        q.append(next)\n\n        return res\n\n```
['Python3']