O(n^3) algorithm
Intuition\n Describe your first thoughts on how to solve this problem. \nA (sub)tree may have many diameters, but there is exactly one or two centers. To simplf
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nA (sub)tree may have many diameters, but there is exactly one or two centers. To simplfying the implementation, we divide into two cases: diameter is even or odd. For the case of even diameter, we  count the subtrees by enumerating each vertex as the center. For the case of odd diameter, we enumerate each edge as the center. \n# Approach\n<!-- Describe your approach to solving the problem. -->\nFor each node $v$ as the center, we root the tree at $v$ and do a DFS. When visiting a vertex $u$, we recursively compute the number of subtrees rooted at $u$ and with depth $i$, for each possible $i$.\nWhen combining the results from the children of $u$, a naive implementation takes $O(deg(u)\\times n^2)$ time. By using prefix sum, it can be reduced to $O(deg(u)\\times n)$ time. Thus a DFS takes $O(n^2)$ since the total degree of a tree is $O(n)$.\nAt root $v$, we combine the results from its children. Since we care about only even diameter and centered at $v$, two branches of same depth $i$ form a subtree of diamter $2i$. When combining the branches one by one, we need to count the way that a current subtree is merged with a small incoming subtree which does not change its diameter.\nThe case of odd diameter is similar and simpler since there are only two branches for each center edge.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$O(n^3)$ since each center vertex takes $O(n^2)$.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nLinear.\n\n# Code\n```\nclass Solution:\n    # odd/even diameter couned individually\n    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n        adj = [[] for i in range(n)]\n        for u,v in edges:\n            adj[u-1].append(v-1)\n            adj[v-1].append(u-1)\n        def comb(p,q): # merge p and q, res[max(i,j)]+=p[i]*q[j]\n            if len(q)<len(p): p,q = q,p\n            res = [0]*len(q)\n            res[0] = p[0]*q[0]\n            for i in range(1,len(p)): p[i] += p[i-1]\n            for i in range(1,len(q)): q[i] += q[i-1]\n            for i in range(1,len(p)):\n                res[i] = p[i]*q[i]-p[i-1]*q[i-1]\n            for i in range(len(p),len(q)):\n                res[i] = (q[i]-q[i-1])*p[-1]\n            return res\n            \n        def dfs(r,p): # num of subtree rooted at r with given depth\n            d = [1]\n            for v in adj[r]:\n                if v==p: continue\n                t = [1]+dfs(v,r)\n                d = comb(t,d)\n            return d\n        #end dfs\n        ans = [0]*n\n        # odd diameter with (u,v) as center edge\n        for u,v in edges:\n            u -= 1; v-=1\n            p = dfs(u,v)\n            q = dfs(v,u)\n            for i in range(min(len(p),len(q))):\n                ans[i+i+1] += p[i]*q[i]\n        #even diamter with v as center vertex\n        for v in range(n): \n            if len(adj[v])==1: continue \n            tree = [1]+dfs(adj[v][0],v) #tree with depth\n            curr = [0]*n\n            for u in adj[v][1:]:\n                q = [1]+dfs(u,v)\n                # curr tree + new small\n                j = 1; t = q[1]+1 # prefix sum of q\n                for i in range(4,n,2):\n                    while j+1<min(i//2,len(q)):\n                        j += 1; t += q[j]\n                    curr[i] *= t\n                # curr tree + same height\n                for i in range(min(len(tree),len(q))):\n                    curr[i+i] += tree[i]*q[i]\n                tree = comb(tree,q)\n            for i in range(2,n,2):\n                ans[i] += curr[i]\n        #end\n        return ans[1:]\n\n\n```\n
['Python3']