[JAVA] O(n*(2^n)) backtracking solution with detailed explanation.
Idea: Using backtracking choose which vertex is to be included and which is not. If it forms a valid tree, find the maximum distance between two nodes in it.\n\
Idea: Using backtracking choose which vertex is to be included and which is not. If it forms a valid tree, find the maximum distance between two nodes in it.\n```\nclass Solution {\n    public int[] countSubgraphsForEachDiameter(int n, int[][] edges) {\n        boolean []isIncluded=new boolean[n+1]; // to determine which vertex is included in the subset and which is not.\n        \n        // edge list\n        List<List<Integer>> list=new ArrayList<>();\n        for(int i=0;i<=n;i++)\n            list.add(new ArrayList<>());\n        \n        // creating the edges\n        for(int []e:edges){\n            list.get(e[0]).add(e[1]);\n            list.get(e[1]).add(e[0]);\n        }\n        \n        int []ans=new int [n-1]; // to store the answer.\n        \n        helper(1,isIncluded,list,n,ans);\n        return ans;\n    }\n    public void helper(int i, boolean []isIncluded, List<List<Integer>> list, int n, int[] ans){\n        // This function selects which vertex is included and which is not, by backtracking.\n        \n        if(i==n+1){\n            int val=find(isIncluded,n,list); // returns -1 if the subtree is not connected or consists of a single vertex or is an empty tree. \n            if(val>0)\n                ans[val-1]++;            \n            return;\n        }\n        \n        helper(i+1,isIncluded,list,n,ans); // vertex is not included.\n        isIncluded[i]=true;\n        helper(i+1,isIncluded,list,n,ans); // vertex is included.\n        isIncluded[i]=false; // backtracking step.        \n    }\n    \n    int max=0; // to store the max distance between any two nodes.\n    public int find(boolean []isIncluded, int n, List<List<Integer>> list){\n        int cnt=0,root=-1;\n        \n        // counting the number of included vertices and choosing the first included vertex as the root(any included vertex can be chosen as the root).\n        for(int i=1;i<=n;i++){\n            if(isIncluded[i]){\n                if(root==-1)\n                    root=i;\n                cnt++;\n            }\n        }\n        \n        // if the number of vertices are less than or equal to 1, i.e., either the tree is empty or consists of a single vertex.\n        if(cnt<=1)\n            return -1;\n        \n        max=0;// initialising the global variable.\n        \n        boolean []vis=new boolean[n+1]; // to find every included vertex is reachable or not.\n        \n        maxDist(root,list,isIncluded,vis); \n        \n        // to see if any vertex is unreachable from the root.\n        for(int i=1;i<=n;i++)\n            if(isIncluded[i]&&!vis[i]) // if unreachable, return -1, as the subtree is not connected.\n                return -1;        \n        \n        return max; // returning maximum distance between two nodes in the subtree.\n    }\n    public int maxDist(int i, List<List<Integer>> list, boolean []isIncluded, boolean []vis){\n        /*\n            first: to store the largest path in the subtree treating the current vertex as the root.\n            second: to store the second-largest path in the subtree treating the current vertex as the root.\n        */\n        int first=0, second=0,val;\n        vis[i]=true;\n        \n        for(int j:list.get(i)){\n            if(isIncluded[j]&&!vis[j]){ // we can visit a vertex only if it is included in the current subtree.\n                val=maxDist(j,list,isIncluded,vis);\n                if(val>first){\n                    second=first;\n                    first=val;\n                }\n                else if(val>second)\n                    second=val;\n            }\n        }\n        max=Math.max(max,first+second); // updating the max value.\n        return first+1;\n    }\n}\n// O(n*(2^n)) Time Complexity.\n```\nThanks for reading. Please upvote.
[]