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;
	}
};