Node Level DP
Code\njava []\nclass Solution {\n    public int[] countSubgraphsForEachDiameter(int n, int[][] edges) {\n        Node[] nodes = new Node[n];\n        for (int i
# Code\n```java []\nclass Solution {\n    public int[] countSubgraphsForEachDiameter(int n, int[][] edges) {\n        Node[] nodes = new Node[n];\n        for (int i = 0; i < n; i++) {\n            nodes[i] = new Node(i+1);\n        }\n        for (int[] e : edges) {\n            nodes[e[0]-1].children.add(nodes[e[1]-1]);\n            nodes[e[1]-1].children.add(nodes[e[0]-1]);\n        }\n        int[] res = new int[n - 1];\n        for (Node x: nodes) {\n            for (Map.Entry<Size, Integer> e : x.subtree().entrySet()) {\n                if (e.getKey().span-1 >= 0) {\n                    res[e.getKey().span-1] += e.getValue();\n                }\n            }\n        }\n        return res;\n    }\n\n    static class Node {\n        int i;\n        List<Node> children = new ArrayList<>();\n        boolean visited = false;\n        Map<Size, Integer> subTree;\n\n        Node(int i) {\n            this.i = i;\n        }\n\n        // res[maxDis][depth] ==> number of subtree.\n        public Map<Size, Integer> subtree() {\n            if (subTree != null) {\n                return subTree;\n            }\n            visited = true;\n            Map<Size, Integer> freq = new HashMap<>();\n            freq.put(new Size(0, 0), 1);\n            for (Node c : children) {\n                if (c.visited) {\n                    continue;\n                }\n                Map<Size, Integer> childFreq = c.subtree();\n                Map<Size, Integer> newFreq = new HashMap<>(freq);\n                for (Map.Entry<Size, Integer> e : freq.entrySet()) {\n                    for (Map.Entry<Size, Integer> ce : childFreq.entrySet()) {\n                        Size exist = e.getKey();\n                        Size child = ce.getKey();\n                        Size s = new Size(\n                                Math.max(Math.max(exist.span, child.span), exist.depth + child.depth + 1),\n                                Math.max(exist.depth, child.depth + 1));\n                        newFreq.put(s, newFreq.getOrDefault(s, 0) + e.getValue() * ce.getValue());\n                    }\n                }\n                freq = newFreq;\n            }\n            subTree = freq;\n            System.out.printf("%d: %s\\n", i, freq);\n            return freq;\n        }\n    }\n\n    static class Size {\n        int span, depth;\n\n        public Size(int s, int d) {\n            span = s;\n            depth = d;\n        }\n\n        public boolean equals(Object o) {\n            if (o instanceof Size) {\n                Size s = (Size) o;\n                return span == s.span && depth == s.depth;\n            }\n            return false;\n        }\n\n        public int hashCode() {\n            return span + depth * 31;\n        }\n\n        public String toString() {\n            return String.format("(%d, %d)", span, depth);\n        }\n    }\n}\n```
['Java']