Java backtracking
Intuition\n Describe your first thoughts on how to solve this problem. \nFinding the longest path in a tree is a common problem, however this problem requires y
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nFinding the longest path in a tree is a common problem, however this problem requires you to compute it for all subtrees. From the definition a subtree is essentially a subset of paths in the tree, with the restriction that all paths needs to be connected. For this reason the number of subtrees is likely exponential. \n\nYou can easily prove that solving for the rooted tree is the same as solving the original problem (all paths {A, ..., ROOT, ..., B} can be written as {ROOT, ..., A} + {ROOT, ..., B} as the order doesn\'t matter).\n\nTo generate all subtrees we can just write a backtracking algorithm where in the decision tree we try to append an edge or not to the current path. Then, the key idea is to recurse on the edges rather than the nodes as you normally would, because the edges is where the decision tree forks.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe need to make a recursive call to all edges. For this reason we cannot implement a DFS like algorithm because if we skip the current edge we still need to recurse on the remaining connected edges. The solution is then to design a BFS algorithm where the fronteer expands or reduces according to backtracking.\n\nTo explore only connected edges we can just create adjacency lists.\n\nOnce all edges have been processed the easiest way to find the longest path is to explicitely build the subtree during recursion and once it is done find the longest path on that new tree\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nThe size of the decision tree. Due to edge connectivity the decision tree is not complete, but we can use the complete decision tree as upper bound.\n\nAll operations in the recursive call take constant time. There is an outer recursion that guesses the root of the subTree, thus recursing n times at most. For each subtree root all possible subtrees are built. Finding the subtree longest path is linear in n.\n$$O(n * 2^(n - 1) * n)$$ = $$O(n^2 * 2^(n - 1))$$\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nThe height of the decision tree. There is one level per edge. Due to edge connectivity the decision tree is not complete, but we can use the complete decision tree as upper bound. Finding the subtree longest path is linear in n.\n$$O(n - 1 + n)$$ = $$O(n)$$\n\n# Code\n```\nclass Solution {\n\n    List<Integer>[] tree, subTree;\n    int subTreeRoot, maxPath;\n    boolean[] inStack; // do not allow to travel upwards in the rooted tree\n    int[] ans;\n\n    public int[] countSubgraphsForEachDiameter(int n, int[][] edges) {\n        buildTree(n, edges);\n        ans = new int[n - 1];\n        solve(0);\n        return ans;\n    }\n\n    private void buildTree(int n, int[][] edges) {\n        tree = new List[n];\n        subTree = new List[n];\n        inStack = new boolean[n];\n        for (int i = 0; i < n; ++i) {\n            tree[i] = new ArrayList<>();\n            subTree[i] = new ArrayList<>();\n        }\n        for (int[] e : edges) {\n            tree[e[0] - 1].add(e[1] - 1);\n            tree[e[1] - 1].add(e[0] - 1);\n        }\n    }\n\n    private void solve(int i) {\n        subTreeRoot = i;\n        inStack[i] = true;\n        buildSubTree(0, 0, Collections.singletonList(i), new ArrayList<>());\n        for (int e : tree[i]) {\n            if (inStack[e]) {\n                continue;\n            } \n            solve(e);\n        }\n    }\n\n    private void buildSubTree(int i, int j, List<Integer> fronteer, List<Integer> next) {\n        if (i >= fronteer.size()) {\n            buildNextLevel(next);\n            return;\n        }\n        int curr = fronteer.get(i);\n        if (j >= tree[curr].size()) {\n            buildSubTree(i + 1, 0, fronteer, next);\n        } else {\n            int succ = tree[curr].get(j);\n            if (inStack[succ]) {\n                buildSubTree(i, j + 1, fronteer, next);\n                return;\n            }\n            inStack[succ] = true;\n            next.add(succ);\n            subTree[curr].add(succ);\n            buildSubTree(i, j + 1, fronteer, next);\n            next.remove(next.size() - 1);\n            subTree[curr].remove(subTree[curr].size() - 1);\n            buildSubTree(i, j + 1, fronteer, next);\n            inStack[succ] = false;\n        }\n    }\n\n    private void buildNextLevel(List<Integer> next) {\n        if (next.isEmpty()) { // subTree is done, add it to the answer\n            maxPath = 0;\n            computeMaxPath(subTreeRoot);\n            if (maxPath > 1) {\n                ++ans[maxPath - 2];\n            }\n        } else {\n            buildSubTree(0, 0, next, new ArrayList<>());\n        }\n    }\n\n    private int computeMaxPath(int i) {\n        int max = 0, prevMax = 0;\n        for (int child : subTree[i]) {\n            int h = computeMaxPath(child);\n            if (h >= max) {\n                prevMax = max;\n                max = h;\n            } else {\n                prevMax = Integer.max(prevMax, h);\n            }\n        }\n        maxPath = Integer.max(maxPath, prevMax + max + 1);\n        return max + 1;\n    }\n}\n```
['Java']