题目：
给你 n 个城市，编号为从 1 到 n 。同时给你一个大小为 n-1 的数组 edges ，其中 edges[i] = [ui, vi] 表示城市 ui 和 vi 之间有一条双向边。题目保证任意城市之间只有唯一的一条路径。换句话说，所有城市形成了一棵 树 。

一棵 子树 是城市的一个子集，且子集中任意城市之间可以通过子集中的其他城市和边到达。两个子树被认为不一样的条件是至少有一个城市在其中一棵子树中存在，但在另一棵子树中不存在。

对于 d 从 1 到 n-1 ，请你找到城市间 最大距离 恰好为 d 的所有子树数目。

请你返回一个大小为 n-1 的数组，其中第 d 个元素（下标从 1 开始）是城市间 最大距离 恰好等于 d 的子树数目。

请注意，两个城市间距离定义为它们之间需要经过的边的数目。

方法一：动态规划

思路：

参考B站花花酱的视频：https://www.bilibili.com/video/BV1Ei4y1j7h5/

d：以u为根节点的树的直径
k：根节点u到树中最远节点的距离

1. dp定义：
   dp[i][k][d]: 以i为根节点且直径为d的子树的数量，k是根节点i到子树中最远节点的距离
2. 初始化：
   dp[i][0][0]=1 （仅包含一个节点的树）
3. 状态转移
   dp[u][k][d]=sum(dp[u][k1][d1]*dp[u][k2][d2])，其中：k=max(k1，k2+1)，d=max(d1，d2，k1+k2+1)

解答：
暂时略

方法二：任意两点之间的距离

思路：
参见leetcode官方题解方法三

解答：

class Solution:def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:#建树g=[[] for _ in range(n)]#将编号调整为从0开始for x,y in edges:g[x-1].append(y-1)g[y-1].append(x-1)#计算树上任意两点间的距离dis=[[0]*n for _ in range(n)]def dfs(x,fa):for y in g[x]:if y!=fa:dis[i][y]=dis[i][x]+1 #自顶向下dfs(y,x)for i in range(n):dfs(i,-1) #计算i到其余点的距离def dfs2(x,fa):#能递归到这，说明x可以选cnt=1 #选xfor y in g[x]:#and的优先级要高于or,为了防止重复计算，此处作了优化if y!=fa and (di[y]j) and (dj[y]i):cnt*=dfs2(y,x)  #每棵子树独立if di[x]+dj[x]>d: #x是可选点cnt+=1  #不选x,空树return cntans=[0]*(n-1)for i,di in enumerate(dis):for j in range(i+1,n):dj=dis[j]d=di[j]ans[d-1]+=dfs2(i,-1)return ans