[Python] Floyd Warshall and check all subtrees
Uses the Floyd-Warshall algortihm to calculate the shortest path between each pair of nodes.  We then check each of the 2^N subtrees of the tree.  If the subtre
Uses the Floyd-Warshall algortihm to calculate the shortest path between each pair of nodes.  We then check each of the 2^N subtrees of the tree.  If the subtree is connected (checked by performing BFS and checking if all nodes in the subgraph are visisted), then the maximum distance is found using the results from the Floyd-Warshall algoriths.  I thought this would be somewhat slow, but it beats ~83% of the entries.\n\n```\nclass Solution:\n    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n        def all_distances(n, edges):\n            D = [[10 ** 5] * n for _ in range(n)]\n            for u, v in edges:\n                D[u-1][v-1] = 1\n                D[v-1][u-1] = 1\n            for v in range(n):\n                D[v][v] = 0\n            \n            for k in range(n):\n                for i in range(n):\n                    for j in range(n):\n                        D[i][j] = min(D[i][j], D[i][k] + D[k][j])\n            return D\n        \n        def make_graph(n, edges):\n            G = [[] for _ in range(n)]\n            for u, v in edges:\n                G[u-1].append(v-1)\n                G[v-1].append(u-1)\n            return G\n        \n        def check_connected(G, include):\n            if not any(include):\n                return False\n            root = include.index(True)\n            visited = [False] * len(G)\n            q = deque([root])\n            visited[root] = True\n            while q:\n                v = q.popleft()\n                for x in G[v]:\n                    if not visited[x] and include[x]:\n                        visited[x] = True\n                        q.append(x)\n            return visited == include\n        \n        def max_distance(D, include):\n            m = 0\n            for i in range(n):\n                if include[i]:\n                    for j in range(i, n):\n                        if include[j]:\n                            m = max(m, D[i][j])\n            return m\n        \n        def rec(include, idx, ans, G, D):\n            if idx == n:\n                if check_connected(G, include):\n                    d = max_distance(D, include)\n                    if d >= 1:\n                        ans[d-1] += 1\n            else:\n                rec(include, idx + 1, ans, G, D)\n                include[idx] = True\n                rec(include, idx + 1, ans, G, D)\n                include[idx] = False\n\n        G = make_graph(n, edges)\n        D = all_distances(n, edges)\n        include = [False] * n\n        ans = [0] * (n-1)\n        \n        rec(include, 0, ans, G, D)\n\n        return ans\n```
[]