[C++/Python] Floyd-Warshall + Enumerate Subsets O(2^N * N^2)
Ideas\n\n There are only 2^15 possible subsets of nodes. We can check them all.\n A subset of size k is a subtree if-and-only-if there are k-1 edges between pai
**Ideas**\n\n* There are only `2^15` possible subsets of nodes. We can check them all.\n* A subset of size `k` is a subtree if-and-only-if there are `k-1` edges between pairs in the subset.\n\n**Algorithm**\n\n1. Use [Floyd-Warshall Algorithm](https://en.m.wikipedia.org/wiki/Floyd\u2013Warshall_algorithm) to find all shortest paths.\n2. Brute force all possible subsets and count subtrees with diameter `d`.\n\n**Python**\n```python\nfrom itertools import combinations, permutations\n\nclass Solution:\n    def countSubgraphsForEachDiameter(self, n, edges):\n        g = [[999 for _ in range(n)] for _ in range(n)]\n        for [i, j] in edges:\n            g[i - 1][j - 1], g[j - 1][i - 1] = 1, 1\n\n        for k, i, j in permutations(range(n), 3):\n            g[i][j] = min(g[i][j], g[i][k] + g[k][j])\n\n        ans = [0 for _ in range(n - 1)]\n        for k in range(2, n + 1):\n            for s in combinations(range(n), k):\n                e = sum(g[i][j] for i, j in combinations(s, 2) if g[i][j] == 1)\n                d = max(g[i][j] for i, j in combinations(s, 2))\n                if e == k - 1:\n                    ans[d - 1] += 1\n        \n        return ans\n```\n**C++**\n```c++\nclass Solution {\npublic:\n    vector<int> countSubgraphsForEachDiameter(int n, vector<vector<int>>& edges) {\n        vector<vector<int>> g(n, vector<int>(n, 999));\n        for (auto &e : edges) {\n            int i = e[0] - 1;\n            int j = e[1] - 1;\n            g[i][j] = g[j][i] = 1;\n        }\n        \n        for (int k = 0; k < n; k++) {\n            for (int i = 0; i < n; i++) {\n                for (int j = 0; j < n; j++) {\n                    g[i][j] = min(g[i][j], g[i][k] + g[k][j]);\n                }\n            }\n        }\n        \n        vector<int> ans(n - 1, 0);\n        for (int s = 0; s < (1 << n); s++) {\n            int k = __builtin_popcount(s);\n            int e = 0;\n            int d = 0;\n            for (int i = 0; i < n; i++) if (s & (1 << i)) {\n                for (int j = i + 1; j < n; j++) if (s & (1 << j)) {\n                    e += g[i][j] == 1;\n                    d = max(d, g[i][j]);\n                }\n            }\n            if (e == k - 1 && d > 0) {\n                ans[d - 1]++;\n            }\n        }\n        \n        return ans;\n    }\n};\n```\nNote: `__builtin_popcount(s)` gets the number of 1 bits in `s`.
[]