Bitmask | Diameter of tree | C++ | clean code | easiest approach
Approach\n Describe your approach to solving the problem. \n1. Traverse through each possible subset using bitmask\n2. Ignore the mask which contains only one n
# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Traverse through each possible subset using bitmask\n2. Ignore the mask which contains only one node or the graph is not connected.\n    + for one node use :    `(i&(i-1)) == 0` [mask must be in powers of 2]\n    + for graph with more than one components : check the number of nodes which can be visited and it should be not be equal to number of set bits in mask\n3. Now the mask would surely be containing valid tree, just find diameter of it and increment the answer array.\n\n# Code\n```\nclass Solution {\npublic:\n    vector<vector<int>> g;\n    vector<int> ans;\n    int count_set_bits(int mask)\n    {\n        int count = 0;\n        while(mask > 0) {count+= ((mask % 2) == 1);mask/=2;}\n        return count;\n    }\n    int check_tree(int mask, int root, int par)\n    {\n        int ans = 1;\n        for(auto &x:g[root])\n        {\n            if(x == par ||( (mask & (1<<x)) == 0)) continue;\n            ans += check_tree(mask, x, root);\n        }\n        return ans;\n    }\n    int dfs(int mask ,int root, int par, vector<int> &lev)\n    {\n        int child = root;\n        for(auto &x:g[root])\n        {\n            if(x == par || ((mask & (1<<x)) == 0)) continue;\n            int temp_child = dfs(mask, x, root, lev);\n            if(lev[root] < lev[x] + 1) \n            {\n                lev[root] = lev[x] + 1; \n                child = temp_child;\n            }\n        }\n        return child;\n    }\n    int diameter(int mask, int root, int n)\n    {\n        vector<int> lev(n,0);\n        int deepest_node = dfs(mask, root, -1, lev);\n        lev.assign(n,0);\n        dfs(mask, deepest_node, -1, lev);\n        return lev[deepest_node];\n    }\n    vector<int> countSubgraphsForEachDiameter(int n, vector<vector<int>>& edges) {\n        g.resize(n);\n        ans.resize(n-1);\n        for(auto &x:edges) \n        {\n            g[x[0] - 1].push_back(x[1] - 1);\n            g[x[1] - 1].push_back(x[0] - 1);\n        }\n        for(int i = 1;i<(1<<n);i++)\n        {\n            if((i&(i-1)) == 0 || check_tree(i, log2(i&(-i)), -1) != count_set_bits(i)) continue;\n            int dia = diameter(i, log2(i&(-i)), n);\n            ans[dia - 1]++;\n        }\n        return ans;\n    }\n};\n```
['C++']