func countSubgraphsForEachDiameter(n int, edges [][]int) []int {
// 建树
g := make([][]int, n)
for _, e := range edges {
x, y := e[0]-1, e[1]-1 // 编号改为从 0 开始
g[x] = append(g[x], y)
g[y] = append(g[y], x)
}
// 计算树上任意两点的距离
dis := make([][]int, n)
for i := range dis {
// 计算 i 到其余点的距离
dis[i] = make([]int, n)
var dfs func(int, int)
dfs = func(x, fa int) {
for _, y := range g[x] {
if y != fa {
dis[i][y] = dis[i][x] + 1 // 自顶向下
dfs(y, x)
}
}
}
dfs(i, -1)
}
ans := make([]int, n-1)
for i, di := range dis {
for j := i + 1; j < n; j++ {
dj := dis[j]
d := di[j]
var dfs func(int, int) int
dfs = func(x, fa int) int {
// 能递归到这，说明 x 可以选
cnt := 1 // 选 x
for _, y := range g[x] {
if y != fa &&
(di[y] < d || di[y] == d && y > j) &&
(dj[y] < d || dj[y] == d && y > i) { // 满足这些条件就可以选
cnt *= dfs(y, x) // 每棵子树互相独立，采用乘法原理
}
}
if di[x]+dj[x] > d { // x 是可选点
cnt++ // 不选 x
}
return cnt
}
ans[d-1] += dfs(i, -1)
}
}
return ans
}
class Solution {
private List<Integer>[] g;
private int[][] dis;
public int[] countSubgraphsForEachDiameter(int n, int[][] edges) {
g = new ArrayList[n];
Arrays.setAll(g, e -> new ArrayList<>());
for (var e : edges) {
int x = e[0] - 1, y = e[1] - 1; // 编号改为从 0 开始
g[x].add(y);
g[y].add(x); // 建树
}
dis = new int[n][n];
for (int i = 0; i < n; ++i)
dfs(i, i, -1); // 计算 i 到其余点的距离
var ans = new int[n - 1];
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j)
ans[dis[i][j] - 1] += dfs2(i, j, dis[i][j], i, -1);
return ans;
}
private void dfs(int i, int x, int fa) {
for (int y : g[x])
if (y != fa) {
dis[i][y] = dis[i][x] + 1; // 自顶向下
dfs(i, y, x);
}
}
private int dfs2(int i, int j, int d, int x, int fa) {
// 能递归到这，说明 x 可以选
int cnt = 1; // 选 x
for (int y : g[x])
if (y != fa &&
(dis[i][y] < d || dis[i][y] == d && y > j) &&
(dis[j][y] < d || dis[j][y] == d && y > i)) // 满足这些条件就可以选
cnt *= dfs2(i, j, d, y, x); // 每棵子树互相独立，采用乘法原理
if (dis[i][x] + dis[j][x] > d) // x 是可选点
++cnt; // 不选 x
return cnt;
}
}
'''
枚举直径端点 + 乘法原理
'''
class Solution:
def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:
# 建树
g = [[] for _ in range(n)]
for x, y in edges:
g[x - 1].append(y - 1)
g[y - 1].append(x - 1) # 编号改为从 0 开始
# 计算树上任意两点的距离
dis = [[0] * n for _ in range(n)]
def dfs(x: int, fa: int) -> None:
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: int, fa: int) -> int:
# 能递归到这，说明 x 可以选
cnt = 1 # 选 x
for y in g[x]:
if y != fa and \
(di[y] < d or di[y] == d and y > j) and \
(dj[y] < d or dj[y] == d and y > i): # 满足这些条件就可以选
cnt *= dfs2(y, x) # 每棵子树互相独立，采用乘法原理
if di[x] + dj[x] > d: # x 是可选点
cnt += 1 # 不选 x
return cnt
ans = [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
func countSubgraphsForEachDiameter(n int, edges [][]int) []int {
// 建树
g := make([][]int, n)
for _, e := range edges {
x, y := e[0]-1, e[1]-1 // 编号改为从 0 开始
g[x] = append(g[x], y)
g[y] = append(g[y], x)
}
// 求树的直径
var inSet, vis [15]bool
var diameter int
var dfs func(int) int
dfs = func(x int) (maxLen int) {
vis[x] = true
for _, y := range g[x] {
if !vis[y] && inSet[y] {
ml := dfs(y) + 1
diameter = max(diameter, maxLen+ml)
maxLen = max(maxLen, ml)
}
}
return
}
ans := make([]int, n-1)
var f func(int)
f = func(i int) {
if i == n {
for v, b := range inSet {
if b {
vis, diameter = [15]bool{}, 0
dfs(v)
break
}
}
if diameter > 0 && vis == inSet {
ans[diameter-1]++
}
return
}
// 不选城市 i
f(i + 1)
// 选城市 i
inSet[i] = true
f(i + 1)
inSet[i] = false // 恢复现场
}
f(0)
return ans
}
func max(a, b int) int { if a < b { return b }; return a }
