题目描述

给你 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) 所表示的边互不相同。$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Solution {
public:
	vector<int> countSubgraphsForEachDiameter(int n, vector<vector<int>>& edges) {
		vector<int> ans(n - 1);
		vector<vector<int>> G(n + 1);
		vector<int> vis(n + 1);	//访问树
		vector<int> ins(n + 1);	//子树
		int dim = 0;//直径

		for (auto& e : edges) {
			G[e[0]].push_back(e[1]);
			G[e[1]].push_back(e[0]);
		}
		
        //深搜，用于统计直径
        //depu是当前节点u的深度，depv是遍历子节点v后返回的子树的深度
		function<int(int)> DFS = [&](int u) {
			int depu = 0;
			vis[u] = true;
			for (auto& v : G[u]) {
				if (!vis[v] && ins[v]) {
					int depv = DFS(v) + 1;//depv为子树的长度
					dim = max(dim, depu + depv);	//如果子树深度+节点u深度>当前直径，更新当前直径，确保最终含有节点u的子树的直径为最大直径
					depu = max(depu, depv);		//子树深度若增加，更新节点u深度

				}
			}
			return depu;
		};
		
        //回溯函数，用于枚举子树选择
		function<void(int)> _stat = [&](int i) {
			if (i > n) {//完成所有节点的0(不在子树中) 1((在子树中)枚举
				for (int v = 1; v <= n; v++)
					if (ins[v]) {
						for (auto& vs : vis)vs = false;
						dim = 0;//直径
						DFS(v);//获取子树直径
						break;
					}
				if (dim && vis == ins)//获取到直径，且所 选择的树 与 访问树 相同
					ans[dim - 1]++;
				return;
			}

			_stat(i + 1);//子树，不选择节点i
			ins[i] = true;
			_stat(i + 1);//子树，选择节点i
			ins[i] = false;//回溯
		};

		_stat(1);
		for (auto& i : ans) {
			cout << i << " ";
		}
		return ans;
	}
};