If you find it is difficult to understand the solution of this problem like me,
Hope my post can help you to clearly understand the solution. \n\n1. You should first solve problem #543 diameter of binary tree. \n\nGiven one and only one tre
Hope my post can help you to clearly understand the solution. \n\n1. You should first solve problem #543 diameter of binary tree. \n\nGiven one and only one tree, you should be able to understand how we leverage DFS to traverse the tree in postorder fashion and calculate the diameter THROUGH a/every single node to get the diameter which is simply concatenate left and right together\n\n2. Now you can move on to #1245 Tree Diameter\n\nIn this problem, the difference/difficult is, now, we don\'t just have a BINARY tree, we actually have a graph, since a node in this graph not just have left child and right child, we should pick the TOP TWO max incoming path and concatenate them together (other than simply add left + right) \n\nWe need to iterate every neighbor of the current node to get the max diameter through that node. \n\n3. 1617. Count Subtrees With Max Distance Between Cities\n\nNow, we  don\'t just have one graph/tree,  we have to exaustive every subtree/subset. \n(Now you need to review another knowledge if you don\'t possess -- bitmasking) \n\nYou need to get back to #78 subsets to understand how to use bitmasking to contruct subset, once you understand the j & 1<<i, things are much easier now. \n\nNow to solve this problem is only put the above code snippet together. \n\nHope it helps, thanks. \n\n```\nclass Solution {\n    int max = 0;\n    \n    public int[] countSubgraphsForEachDiameter(int n, int[][] edges) {\n        \n        //result[] = {1-indexed ... };\n        \n        int [] result = new int[n-1];\n        //build graph\n        Map<Integer, List<Integer>> graph = new HashMap<>();\n        for(int[] e : edges ){\n            graph.computeIfAbsent(e[0], (k)->(new ArrayList<>())).add(e[1]);\n            graph.computeIfAbsent(e[1], (k)->(new ArrayList<>())).add(e[0]);\n        }\n        \n        //Get all the valid subtrees/subsets \n        for(int i = 0; i < (1 << n); i++){\n            List<Integer> subtree = new ArrayList<>();\n            //use bitmasking to construct every single subset/subtree\n            for(int j = 0; j < n; j++){\n                if((i & (1 << j)) != 0 ) //this bit is 1, means this node is chosen \n                    subtree.add(j + 1); //cities numbered from 1 \n            }\n            \n           \n            //now we need to evaluate if this subtree is valid\n            int edge_number = 0;\n            for(int[] e : edges ){\n                if(subtree.contains(e[0]) && subtree.contains(e[1]))\n                    edge_number ++;\n            }\n            \n            if(edge_number < 1 || subtree.size() != edge_number + 1 )\n                continue; //not valid subtree\n            \n            //till here, we have a valid subtree, and we need to use DFS to get the max diameter\n            Set<Integer> visited = new HashSet<>();\n            max = 0;\n            visited.add(subtree.get(0));\n            dfs(subtree.get(0), graph, subtree, visited); \n            result[max - 1]++;\n        }\n        \n        return result;\n    }\n    \n    private int dfs( int current, Map<Integer, List<Integer>> graph, List<Integer> subtree, Set<Integer> visited){\n        \n        int m1 = 0;\n        int m2 = 0;\n        \n        for(int neighbor : graph.get(current)){\n            if(!visited.contains(neighbor) && subtree.contains(neighbor) ){\n                visited.add(neighbor);\n                int depth = dfs(neighbor, graph, subtree, visited);\n                if(depth > m1){\n                    m2 = m1;\n                    m1 = depth;\n                }else if(depth > m2)\n                    m2 = depth;\n            }\n               \n        }\n        \n        max = Math.max(max, m1 + m2);\n        return m1+1;\n    }\n}\n```\n\n\n\n\n\n\n\n\n\n\n\n\n\n
[]