文章目录
1. 题目
给你 n 个城市，编号为从 1 到 n 。同时给你一个大小为 n-1 的数组 edges ，其中 edges[i] = [ui, vi] 表示城市 ui 和 vi 之间有一条双向边。
题目保证任意城市之间只有唯一的一条路径。换句话说，所有城市形成了一棵 树 。
一棵 子树 是城市的一个子集，且子集中任意城市之间可以通过子集中的其他城市和边到达。
两个子树被认为不一样的条件是至少有一个城市在其中一棵子树中存在，但在另一棵子树中不存在。
对于 d 从 1 到 n-1 ，请你找到城市间 最大距离 恰好为 d 的所有子树数目。
请你返回一个大小为 n-1 的数组，其中第 d 个元素（下标从 1 开始）是城市间 最大距离 恰好等于 d 的子树数目。
请注意，两个城市间距离定义为它们之间需要经过的边的数目。
示例 1：
输入：n
= 4, edges
= [[1,2],[2,3],[2,4]]
输出：
[3,4,0]
解释：
子树
{1,2}, {2,3} 和
{2,4} 最大距离都是
1 。
子树
{1,2,3}, {1,2,4}, {2,3,4} 和
{1,2,3,4} 最大距离都为
2 。
不存在城市间最大距离为
3 的子树。示例
2：
输入：n
= 2, edges
= [[1,2]]
输出：
[1]示例
3：
输入：n
= 3, edges
= [[1,2],[2,3]]
输出：
[2,1]提示：
2 <= n
<= 15
edges
.length
== n
-1
edges
[i
].length
== 2
1 <= ui
, vi
<= n
题目保证
(ui
, vi
) 所表示的边互不相同。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-subtrees-with-max-distance-between-cities
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题
类似题目：LeetCode 1245. 树的直径（图的最大直径结论）
- 先回溯生成所有的子集的可能
- 对每个子集，判断所有点是否联通
- 再计算联通图的最大直径
选择任意一点A开始bfs，记录最后遍历到的点B从B开始bfs遍历，最后到达的点C，BC的距离就是最大直径
class Solution {vector
<int> ans
;vector
<vector
<int>> g
;vector
<int> sub
;int N
;
public:vector
<int> countSubgraphsForEachDiameter(int n
, vector
<vector
<int>>& edges
) {N
= n
;sub
= vector
<int> (n
, 0);ans
= vector
<int> (n
-1, 0);g
.resize(n
);for(auto& e
: edges
){g
[e
[0]-1].push_back(e
[1]-1);g
[e
[1]-1].push_back(e
[0]-1);}dfs(0);return ans
;}void dfs(int i
){if(i
== N
){int d
= calculateD();if(d
!= -1)ans
[d
-1]++;return;}dfs(i
+1);sub
[i
] = 1;dfs(i
+1);sub
[i
] = 0;}int calculateD(){int start
= -1;for(int i
= 0; i
< N
&& start
== -1; ++i
)if(sub
[i
] == 1)start
= i
;int last
= bfs(start
, true);if(last
== -1)return -1;return bfs(last
, false);}int bfs(int id
, bool option
){int count
= 0, total
= accumulate(sub
.begin(),sub
.end(),0);if(total
<= 1)return -1;int last
, size
, step
= 0;vector
<int> unvis(sub
);queue
<int> q
;q
.push(id
);unvis
[id
] = 0;while(!q
.empty()){size
= q
.size();while(size
--){last
= id
= q
.front();q
.pop();count
++;for(int nt
: g
[id
]){if(unvis
[nt
]){unvis
[nt
] = 0;q
.push(nt
);}}}step
++;}if(option
== true){if(count
!= total
)return -1;return last
;}else{return step
-1;}}
};
1140 ms 399.6 MB
我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！
总结
以上是生活随笔为你收集整理的LeetCode 1617. 统计子树中城市之间最大距离（枚举所有可能+图的最大直径）的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。
