BFS + bitmask, iterating all subsets
Intuition\n Describe your first thoughts on how to solve this problem. \n- First thing to do for all questions is to check constraints. For this, n <= 16 meanin
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- First thing to do for all questions is to check constraints. For this, $$n <= 16$$ meaning that total no of possible subtrees can be `$$2^N$$ which is  ~$$10^5$$. This means a bruteforce way is on the cards\n- As the input is a tree, there\'s only a single fixed way to travel between given two nodes, meaning that the distance and path between nodes is fixed. Also, a catch is to figure out that we only need the nodes which are present on the path between start and end nodes, and not their sequence. \n- from above statement, it also follows that the path between any pair of nodes in a subtree must only go through nodes in that subtree, as by definition all nodes in a tree are connected. This can help to identify valid subtrees \n- only having 16 nodes gives the possibility to store each subtree/path in a single int value, saving a ton of space and time \nGenerate Note: anytime there\'s a limitation to max 64 values (no of nodes, size of array/string, etc), always think about storing any temporary data you need as bits on an integer. Works 90% of the time\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- convert the edge list into an adjacency list\n- Precomputing all paths is done using a modified BFS which keeps track of current node as well as all nodes that we have travelled across on the way. \nDistance between two nodes = no of nodes in the path - 1\n- We iterate over all possible subtrees. For each, we make sure that the subtree is valid by checking that the path for each pair of nodes only passes through the subtree. We calculate max distance between 2 nodes in the subtree and maintain that in the result array\n\n# Complexity\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n- creating adjacency list takes $$O(N)$$\n- modifed BFS takes  $$O(N * (E + N))$$ => $$O(N^2)$$ as for a tree $$E = N - 1$$\n- total subtrees =  $$2^N $$. iterating over all pair of nodes in a subtree takes $$O(N^2)$$. So this step takes $$O(N^2*2^N)$$\n- final complexity = $$O(N + N^2 + N^2*2^N)$$ => $$O(N^2*2^N)$$\n# Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n- adjacency list takes $$O(E)$$\n- path matrix takes $$O(N^2)$$\n- - final Complexity = $$O(N^2)$$\n# Code\n```cpp []\nclass Solution {\npublic:\n    vector<int> countSubgraphsForEachDiameter(int n, vector<vector<int>>& edges) {\n        vector<vector<int>> path(n, vector<int> (n, -1));\n        vector<vector<int>> adjacency_list(n, vector<int> {});\n        vector<int> result(n - 1, 0);\n\n        for(int i=0;i<edges.size();i++) {\n            int x = edges[i][0] - 1, y = edges[i][1] - 1;\n            adjacency_list[x].push_back(y);\n            adjacency_list[y].push_back(x);\n        }\n\n        for(int i=0;i<n;i++) {\n            vector<bool> seen(n, false);\n            queue<vector<int>> q;\n            q.push(vector<int> {i, 1 << i});\n            while(!q.empty()) {\n                for(int j=q.size();j>0;j--){\n                    int curr = q.front()[0], curr_nodes = q.front()[1];\n                    q.pop();\n\n                    if (seen[curr]) continue;\n                    seen[curr] = true, path[i][curr] = curr_nodes;\n                    for(int next : adjacency_list[curr]) {\n                        if (!seen[next]) q.push(vector<int> {next, curr_nodes | (1 << next)});\n                    }\n                }\n            }\n        }\n\n        for(int tree=0;tree<(1 << n);tree++) {\n            int max_dist = 0;\n            bool valid_tree = true;\n            for(int n1=0;n1<n;n1++) {\n                if (!(tree & (1 << n1))) continue;\n                for(int n2=0;n2<n;n2++) {\n                    if (!(tree & (1 << n2))) continue;\n                    if ((tree & path[n1][n2]) != path[n1][n2]) {\n                        valid_tree = false;\n                        break;\n                    }\n                    max_dist = max(max_dist, __builtin_popcount(path[n1][n2]) - 1);\n                }\n                if (!valid_tree) break;\n            }\n\n            if (valid_tree && max_dist > 0) {\n                result[max_dist - 1]++;\n            }\n        }\n\n        return result;\n    }\n};\n```
['Breadth-First Search', 'Bitmask', 'C++']