问题：

给定n个节点，以及节点直接的连线数组edges

已知，这些节点代表城市，这些城市构成一棵树，

即任意两节点都有唯一路径。

求，这些城市中的子树中，各个最大路径的子树个数。

Example 1:
Input: n = 4, edges = [[1,2],[2,3],[2,4]]
Output: [3,4,0]
Explanation:
The subtrees with subsets {1,2}, {2,3} and {2,4} have a max distance of 1.
The subtrees with subsets {1,2,3}, {1,2,4}, {2,3,4} and {1,2,3,4} have a max distance of 2.
No subtree has two nodes where the max distance between them is 3.

Example 2:
Input: n = 2, edges = [[1,2]]
Output: [1]

Example 3:
Input: n = 3, edges = [[1,2],[2,3]]
Output: [2,1]
 
Constraints:
2 <= n <= 15
edges.length == n-1
edges[i].length == 2
1 <= ui, vi <= n
All pairs (ui, vi) are distinct.

Example 1:

 

⚠️ 注意：Example 1中所有的子树（至少有两个城市）有：

[1,2] [2,3] [2,4]

[1,2,3] [1,2,4]

[1,2,3,4]

而：

[1,3] [1,4] [1,3,4]没有全联通，因此不算子树。

 

解法：bitmask->Combination 组合。

例如：state：1101

代表组合：[1,2,4]

代码做法：

//遍历n个元素的组合： 
       for(int state=0; state<(1<<n); state++) {
            //bitmask to get combination
            ...
        }
//翻译对应组合：
        for(int i=0; i<n; i++) {//对应元素 i: 0,1,2...n-1
            //this node i doesn't exist.
            if(((state>>i)&1) == 0) continue;
            //this node i exists.
            if(((state>>i)&1) == 1) {
                 ...
            }
        }

 

本题解法：

根据给出的【节点直接的连线数组edges】

1. 创建任意两节点的距离数组distance：

  <1> 直接相连距离： 距离=1

distance[i][j] == distance[j][i]

由于节点无向，因此交换也保存。

  <2> 间接相连距离构建：距离=

distance[i][j] = distance[i][k] + distance[k][j]

 

2. 遍历所有组合：

找到合法子树（node数==edge数+1）

求最大距离。

 

代码参考：

 1 class Solution {
 2 public:
 3     vector<vector<int>> distance;
 4     int getmaxdis(int state, int n) {//this state comb:0~n
 5         //state: 01101
 6         //city:  01234->{1,2,4}
 7         int maxdis = 0;
 8         int city_n = 0, edge_n = 0;
 9         for(int i=0; i<n; i++) {
10             if(((state>>i)&1) == 0) continue;//this city i doesn't exist.
11             city_n++;
12             for(int j=i+1; j<n; j++) {
13                 if(((state>>j)&1) == 0) continue;//this city j doesn't exist.
14                 if(distance[i][j]==1)edge_n++;// 2 cities -> 1 edge
15                 maxdis = max(maxdis, distance[i][j]);
16             }
17         }
18         if(city_n!=edge_n+1) return 0;// invalid set which can't be a tree (like ex1: {1,3,4})
19         return maxdis;
20     }
21     vector<int> countSubgraphsForEachDiameter(int n, vector<vector<int>>& edges) {
22         vector<int>res(n-1, 0);
23         int INF = n;//the max value of the set: n
24         distance.resize(n, vector<int>(n, INF));
25         for(vector<int>& edge:edges) {
26             distance[edge[0]-1][edge[1]-1] = 1;
27             distance[edge[1]-1][edge[0]-1] = 1;
28         }
29         //get all distance
30         for(int k=0; k<n; k++) {//过渡节点
31             for(int i=0; i<n; i++) {
32                 for(int j=0; j<n; j++) {
33                     distance[i][j] = min(distance[i][j], distance[i][k]+distance[k][j]);
34                 }
35             }
36         }
37         
38         //for each set, get res
39         for(int state=0; state<(1<<n); state++) {//bitmask to get combination
40             int d = getmaxdis(state, n);
41             if(d>0) res[d-1]++;
42         }
43         
44         return res;
45     }
46 };