[C++] Faster than 100%, 8ms, No Bit Operations, Generate Subtrees Recursively
Rather than using a bitmask, we recursively generate all subtrees of a child and then use another recursion to generate all possible trees using any combination
Rather than using a bitmask, we recursively generate all subtrees of a child and then use another recursion to generate all possible trees using any combination of those subtrees. For each tree, we actually only need it\'s height and it\'s diameter.\nIt\'s slightly harder to code than the other approach of bitmask + tree diameter, but at least you don\'t need the O(N) diamater algorithm.\n\nTime: O(#subtrees * N) , so if it\'s a line it\'s O(N^3), if it\'s a star it\'s O(2^N * N)\n\n```C++\nclass Solution {\npublic:\n    vector<int> countSubgraphsForEachDiameter(int n, vector<vector<int>>& edges) {\n        struct subtree {\n            int height;\n            int diameter;\n        };\n        vector<int> res(n-1, 0);\n        vector<vector<int>> adj(n);\n        for (auto e : edges) {\n            adj[e[0]-1].push_back(e[1]-1);\n            adj[e[1]-1].push_back(e[0]-1);\n        }\n        function<vector<subtree>(int, int)> dfs = [&](int u, int par) {\n            vector<vector<subtree>> children;\n            for (int v : adj[u]) {\n                if (v == par) continue;\n                children.push_back(dfs(v, u));\n            }\n            vector<subtree> trees;\n            int at = 0;\n            function<void(int,int,int,int)> generateTrees = [&](int at, int max_height1, int max_height2, int diam) {\n                if (at == children.size()) {\n\t\t\t\t    // generate new tree based on max_heights and biggest diameter of all used subtrees\n                    int h,d;\n                    if (max_height1 < 0) {\n                        h = 0;\n                        d = 0;\n                    } else if (max_height2 < 0) {\n                        h = max_height1 + 1;\n                        d = max(diam, max_height1 + 1);\n                    } else {\n                        h = max_height1 + 1;\n                        d = max(diam, max_height1 + max_height2 + 2);\n                    }\n                    if (d > 0) {\n                        res[d-1]++;\n                    }\n                    trees.push_back({h,d});\n                } else {\n                    for (int i = 0; i <= children[at].size(); i++) {\n                        if (i == children[at].size()) {\n\t\t\t\t\t\t    // decide not to use any of this child\'s subtrees\n                            generateTrees(at+1, max_height1, max_height2, diam);\n                        } else {\n\t\t\t\t\t\t    // decide to use subtree i of this child\n                            int h = children[at][i].height;\n                            int d = children[at][i].diameter;\n                            int mh1 = max_height1;\n                            int mh2 = max_height2;\n                            if (h > mh1) {\n                                mh2 = mh1;\n                                mh1 = h;\n                            } else if (h > mh2) {\n                                mh2 = h;\n                            } \n                            generateTrees(at+1, mh1, mh2, max(diam, d));\n                        }\n                    }\n                }\n            };\n            generateTrees(0, -1, -1, -1);\n            return trees;\n        };\n        dfs(0, -1);\n        return res;\n    }\n};\n\n```
[]