C++ || Bitmasking || Floyd-Warshall
Intuition\n Describe your first thoughts on how to solve this problem. \nThe goal is to count the number of subgraphs (connected subtrees) in a tree for each po
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe goal is to count the number of subgraphs (connected subtrees) in a tree for each possible diameter. A diameter of a tree is the longest shortest path between any two nodes in that tree. To achieve this, we need to:\n\n1. Identify all possible subgraphs.\n2.\tCheck if each subgraph is a valid tree.\n3.\tCalculate the diameter of each valid tree.\n4.\tCount how many trees have each possible diameter.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1.\tInitialize the Distance Matrix:\n\t\u2022\tCreate a distance matrix dist with large initial values to represent the maximum possible distances between nodes.\n\t\u2022\tSet the distances for the direct edges given in the input to 1.\n2.\tCompute All-Pairs Shortest Paths (Floyd-Warshall Algorithm):\n\t\u2022\tUpdate the distance matrix to store the shortest paths between all pairs of nodes using the Floyd-Warshall algorithm.\n3.\tFunction to Evaluate Subgraph Validity and Diameter (f function):\n\t\u2022\tFor each possible subset of nodes (represented by a bitmask), determine if it forms a valid tree.\n\t\u2022\tIf valid, calculate the maximum distance (diameter) in this subset.\n4.\tCount Subgraphs for Each Diameter:\n\t\u2022\tIterate through all possible subsets of nodes.\n\t\u2022\tUse the f function to determine if each subset is a valid tree and to calculate its diameter.\n\t\u2022\tIncrement the count for the corresponding diameter if the subset is a valid tree.\n\n# Complexity\n- Time complexity: $$O(n^3+2^n*n^2)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n^2)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\nvector<vector<int>> dist;\nprivate:\n    int f(int mask, int n){\n        int node = 0;\n        int edge = 0;\n        int maxi = 0;\n\n        for(int i=0; i<n; i++){ // checking if i\'th node is included in subset\n            if(((mask>>i)&1)==1){\n                node++;\n                for(int j=i+1; j<n; j++){\n                    if(((mask>>j)&1)==1){ // going to all the next included nodes and calculating diameter\n                        if(dist[i][j]==1) edge++;\n                        maxi = max(maxi, dist[i][j]);\n                    }\n                }\n            }\n        }\n\n        // if complete subtree forms return maximum distance, else return -1\n        if(node==edge+1) return maxi;\n        else return -1;\n    }\npublic:\n    vector<int> countSubgraphsForEachDiameter(int n, vector<vector<int>>& edges) {\n\n        dist = vector<vector<int>>(15, vector<int>(15, 1e9));\n        for(auto it: edges){\n            dist[it[0]-1][it[1]-1] = dist[it[1]-1][it[0]-1] = 1;\n        }\n\n        // finding minimum distance between each pair of cities\n        for(int k=0; k<n; k++){\n            for(int i=0; i<n; i++){\n                for(int j=0; j<n; j++){\n                    dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]);\n                }\n            }\n        }\n\n        vector<int> ans(n-1,0);\n\n        for(int i=0; i<(1<<n); i++){\n            int d = f(i,n);\n            if(d>0){\n                ans[d-1]++;\n            }\n        }\n\n        return ans;\n    }\n};\n```
['Dynamic Programming', 'Bit Manipulation', 'Tree', 'Enumeration', 'Bitmask', 'C++']