[Python] DFS and Bit solution with Japanese explanation
Intuition & Approach\n Describe your first thoughts on how to solve this problem. \n- \u6728\u306E\u76F4\u5F84\uFF08\u6700\u9577\u7D4C\u8DEF\uFF09\u306E\u6C42\u
# Intuition & Approach\n<!-- Describe your first thoughts on how to solve this problem. -->\n- \u6728\u306E\u76F4\u5F84\uFF08\u6700\u9577\u7D4C\u8DEF\uFF09\u306E\u6C42\u3081\u65B9\u3092\u77E5\u3063\u3066\u3044\u308B\u5FC5\u8981\u304C\u3042\u308B\u3002\n- \u5168\u3066\u306E\u90E8\u5206\u6728\u306B\u3064\u3044\u3066\u8003\u3048\u308C\u308B\u3053\u3068\u304C\u3067\u304D\u308C\u3070\u826F\u3044\u3002\n- \u3053\u308C\u3092\u5B9F\u73FE\u3059\u308B\u305F\u3081\u306Bbit\u306B\u3088\u3063\u3066\u4F7F\u7528\u3059\u308B\u30A8\u30C3\u30B8\u3092\u8868\u73FE\u3059\u308B\n\n# Complexity\n$$N$$: ```n```\n- Time complexity: $$O(N2^N)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\u5168\u3066\u306E\u30A8\u30C3\u30B8\u306E\u4F7F\u7528\u30D1\u30BF\u30FC\u30F3\u304C$$(2^N)$$\u901A\u308A\u3002\u3000\u3000\n\u305D\u308C\u305E\u308C\u306E\u4F7F\u7528\u3059\u308B\u30A8\u30C3\u30B8\u30D1\u30BF\u30FC\u30F3\u3067\u306E`graph`\u4F5C\u6210\u3001`isTree`\u306B\u3088\u308B\u6728\u5224\u5B9A\u3001`diameter`\u306B\u3088\u308B\u76F4\u5F84\u306E\u8A08\u7B97\u306F\u5168\u3066$$O(N)$$\u3002\u3000\u3000\n\u3088\u3063\u3066\u5168\u4F53\u3067\u306F\u7A4D\u306E$$O(N2^N)$$\u3002\n\n- Space complexity: $$O(N)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n`graph`\u3001`isTree`\u5185\u3067\u306Edfs\u306E\u30B9\u30BF\u30C3\u30AF\u3001`diameter`\u5185\u3067\u306Edfs\u306E\u30B9\u30BF\u30C3\u30AF\u305D\u308C\u305E\u308C\u3067$$O(N)$$\u4F7F\u7528\u3002\n\n# Code\n```python\ndef isTree(graph):\n    N = len(graph)\n    visited = set([])\n\n    # \u9589\u8DEF\u304C\u3042\u308B\u304B\u3092\u8FD4\u3059\n    def dfs(u, parent):\n        visited.add(u)\n\n        # \u9589\u8DEF\u304C\u3042\u308B\u304B\u3092\u5224\u5B9A\n        hasCycle = False\n\n        for v in graph[u]:\n            # \u89AA\u306A\u306E\u3067\u30B9\u30EB\u30FC\n            if v == parent:\n                continue\n\n            # \u5230\u9054\u6E08\u307F\u306E\u5B50\u30CE\u30FC\u30C9\u304C\u3042\u308B\u3068\u3044\u3046\u3053\u3068\u306F\u9589\u8DEF\u304C\u3042\u308B\u3053\u3068\u3092\u610F\u5473\u3059\u308B\n            if v in visited:\n                return True\n\n            hasCycle |= dfs(v, u)\n\n        return hasCycle\n\n    # \u9589\u8DEF\u306A\u3057\u3067\u304B\u3064\u9023\u7D50\u304B\u3092\u78BA\u8A8D\n    return (not dfs(0, -1)) and len(visited) == N\n\ndef diameter(tree_graph):\n    global x, dis\n    x, dis = 0, 0\n\n    # x\u3092\u59CB\u70B9\u3068\u3059\u308B\n    # p: u\u306E\u89AA\u3001d: x\u304B\u3089u\u3078\u306E\u8DDD\u96E2\n    def dfs(u, p, d):\n        global x, dis\n        if d > dis:\n            dis = d\n            x = u\n        for v in tree_graph[u]:\n            if v == p:\n                continue\n            dfs(v, u, d+1)                \n\n    dfs(0, -1, 0)            \n    dis = 0\n    dfs(x, -1, 0)\n    return dis\n\nclass Solution:\n    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n        ans = [0 for _ in range(n-1)]\n\n        # \u3069\u306E\u30A8\u30C3\u30B8\u3092\u4F7F\u3046\u304B\u3092\u5168\u3066\u8003\u3048\u308B\u3001bit\u306B\u3088\u3063\u3066\u8868\u73FE\u3059\u308B\n        for i in range(1 << (n-1)):\n            # \u4F7F\u7528\u3059\u308B\u30A8\u30C3\u30B8\n            use_edges = []\n            nodes = set([])\n            # j\u756A\u76EE\u306Ebit\u304C\u7ACB\u3063\u3066\u3044\u308B\u3068\u304Dedges[j]\u3092\u4F7F\u7528\u3059\u308B\n            for j in range(n-1):\n                if (i >> j) & 1:\n                    use_edges.append(edges[j])\n                    nodes.add(edges[j][0])\n                    nodes.add(edges[j][1])\n\n            N = len(nodes)\n            if N <= 1:\n                continue\n\n            node2node_id = {}\n            for node_id, node in enumerate(list(nodes)):\n                node2node_id[node] = node_id\n\n            # use_edges\u306E\u4E2D\u306E\u30A8\u30C3\u30B8\u306E\u307F\u3067\u4F5C\u3089\u308C\u308B\u30B0\u30E9\u30D5\n            graph = [[] for _ in range(N)]                \n            for edge in use_edges:\n                a, b = edge\n                a_id, b_id = node2node_id[a], node2node_id[b]\n                graph[a_id].append(b_id)\n                graph[b_id].append(a_id)\n\n            # \u6728\u3067\u3042\u308B\u306A\u3089\u305D\u306E\u6700\u9577\u7D4C\u8DEF(\u76F4\u5F84)\u3092\u30AB\u30A6\u30F3\u30C8\n            if isTree(graph):\n                ans[diameter(graph)-1] += 1\n\n        return ans                  \n```
['Python3']