C++ | O(N log N * 2^N) | Bitmask & DFS
Algorithm:\n\nStep 1\nGenerate all subsets (or masks) -> O(2^N)\n\nStep 2\nFor every mask, check if the tree formed is valid or not.\nThis is done by finding th
Algorithm:\n\nStep 1\nGenerate all subsets (or masks) -> O(2^N)\n\nStep 2\nFor every mask, check if the tree formed is valid or not.\nThis is done by finding the number of nodes reachable from one of the nodes using DFS -> O(number of edges in subtree) < O(N) (upper bound)\n\nStep 3\nFor every valid mask, find the diameter of that subtree using DFS + sorting -> O(N log N) (upper bound)\n\nOverall complexity -> O(2^N * NlogN)\n\nCode:\n```\nclass Solution {\npublic:\n    void dfs_cnt(int idx, int par, int& cnt, int mask, vector<vector<int>>& adj_list)\n    {\n        cnt++;\n        for(int i= 0; i< adj_list[idx].size(); i++)\n        {\n            int idx2 = adj_list[idx][i];\n            if(par != idx2 && ((mask>>idx2)&1))\n            {\n                dfs_cnt(idx2, idx, cnt, mask, adj_list);\n            }\n        }\n        return;\n    }\n    bool isMaskValid(int mask, int& idx, int n, vector<vector<int>>& adj_list)\n    {\n        idx=0;\n        while(!(1 & (mask>>idx)))\n            idx++;\n        int exp_cnt = 0;\n        for(int i= 0; i< n; i++)\n            exp_cnt += ((mask>>i)&1);\n        \n        int cnt = 0;\n        dfs_cnt(idx, -1, cnt, mask, adj_list);\n        //cout << "For mask = " << mask << ", exp_cnt = " << exp_cnt << ", cnt = " << cnt << endl;\n        if(cnt == exp_cnt && exp_cnt > 1)\n            return true;\n        return false;\n        \n    }\n    int dfs(int idx, int par, int& d, int mask, vector<vector<int>>& adj_list)\n    {\n        //cout << "Inputs " << idx << ", " << par << endl;\n        vector<int> dist;\n        for(int i= 0; i< adj_list[idx].size(); i++)\n        {\n            int idx2 = adj_list[idx][i];\n            if(par != idx2 && ((mask >> idx2) & 1))\n            {\n                int h = dfs(idx2, idx, d, mask, adj_list);\n                dist.push_back(1+h);\n            }\n        }\n        int ans = 0;\n        \n        if(!dist.empty())\n        {\n            if(dist.size() == 1)\n            {\n                d = max(d, dist[0]);\n                ans = dist[0];\n            }\n            else\n            {\n                sort(dist.begin(), dist.end());\n                int sz = dist.size();\n                int h = dist[sz-1] + dist[sz-2];\n                d = max(h, d);\n                ans = dist[sz-1];\n            }\n        }\n        //cout << "For idx = " << idx << ", par = " << par << ", ans = " << ans << ", d = " << d << endl;\n        return ans;\n    }\n    vector<int> countSubgraphsForEachDiameter(int n, vector<vector<int>>& edges) \n    {\n        vector<vector<int>> adj_list(n, vector<int>());\n        for(int i= 0; i< n-1; i++)\n        {\n            int x = edges[i][0]-1;\n            int y = edges[i][1]-1;\n            adj_list[x].push_back(y);\n            adj_list[y].push_back(x);\n        }\n        \n        vector<int> dp(n-1, 0);\n        \n        for(int mask = 1; mask < (1<<n); mask++)\n        {\n            int idx = 0;\n            if(isMaskValid(mask, idx, n, adj_list))\n            {\n                int d = 0;\n                dfs(idx, -1, d, mask, adj_list);\n                if(d>0) dp[d-1]++;\n            }\n        }\n        return dp;\n    }\n};\n```
['Depth-First Search', 'C', 'Bitmask']