<p>There are <code>n</code> cities numbered from <code>1</code> to <code>n</code>. You are given an array <code>edges</code> of size <code>n-1</code>, where <code>edges[i] = [u<sub>i</sub>, v<sub>i</sub>]</code> represents a bidirectional edge between cities <code>u<sub>i</sub></code> and <code>v<sub>i</sub></code>. There exists a unique path between each pair of cities. In other words, the cities form a <strong>tree</strong>.</p>

<p>A <strong>subtree</strong> is a subset of cities where every city is reachable from every other city in the subset, where the path between each pair passes through only the cities from the subset. Two subtrees are different if there is a city in one subtree that is not present in the other.</p>

<p>For each <code>d</code> from <code>1</code> to <code>n-1</code>, find the number of subtrees in which the <strong>maximum distance</strong> between any two cities in the subtree is equal to <code>d</code>.</p>

<p>Return <em>an array of size</em> <code>n-1</code> <em>where the </em><code>d<sup>th</sup></code><em> </em><em>element <strong>(1-indexed)</strong> is the number of subtrees in which the <strong>maximum distance</strong> between any two cities is equal to </em><code>d</code>.</p>

<p><strong>Notice</strong>&nbsp;that&nbsp;the <strong>distance</strong> between the two cities is the number of edges in the path between them.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<p><strong><img alt="" src="https://assets.leetcode.com/uploads/2020/09/21/p1.png" style="width: 161px; height: 181px;" /></strong></p>

<pre>
<strong>Input:</strong> n = 4, edges = [[1,2],[2,3],[2,4]]
<strong>Output:</strong> [3,4,0]
<strong>Explanation:
</strong>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.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 2, edges = [[1,2]]
<strong>Output:</strong> [1]
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> n = 3, edges = [[1,2],[2,3]]
<strong>Output:</strong> [2,1]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= n &lt;= 15</code></li>
	<li><code>edges.length == n-1</code></li>
	<li><code>edges[i].length == 2</code></li>
	<li><code>1 &lt;= u<sub>i</sub>, v<sub>i</sub> &lt;= n</code></li>
	<li>All pairs <code>(u<sub>i</sub>, v<sub>i</sub>)</code> are distinct.</li>
</ul>
class Solution {
// Used to track farthest node.
int x;
 
// Sets maxCount as maximum distance from node.
void dfsUtil(int node, int count, bool visited[],
                   int& maxCount, list<int>* adj)
{
    visited[node] = true;
    count++;
    for (auto i = adj[node].begin(); i != adj[node].end(); ++i) {
        if (!visited[*i]) {
            if (count >= maxCount) {
                maxCount = count;
                x = *i;
            }
            dfsUtil(*i, count, visited, maxCount, adj);
        }
    }
}
 
// The function to do DFS traversal. It uses recursive
// dfsUtil()
void dfs(int node, int n, list<int>* adj, int& maxCount)
{
    bool visited[n + 1];
    int count = 0;
 
    // Mark all the vertices as not visited
    for (int i = 1; i <= n; ++i)
        visited[i] = false;
 
    // Increment count by 1 for visited node
    dfsUtil(node, count + 1, visited, maxCount, adj);
}
 
// Returns diameter of binary tree represented
// as adjacency list.
int diameter(list<int>* adj, int n, int init)
{
    int maxCount = INT_MIN;
 
    /* DFS from a random node and then see
    farthest node X from it*/
    dfs(init, n, adj, maxCount);
 
    /* DFS from X and check the farthest node
    from it */
    dfs(x, n, adj, maxCount);
 
    return maxCount;
}
 
/* Driver program to test above functions*/
//int main()
//{
//    int n = 5;
// 
//    /* Constructed tree is
//         1
//        / \
//        2    3
//       / \
//      4   5 */
//    list<int>* adj = new list<int>[n + 1];
// 
//    /*create undirected edges */
//    adj[1].push_back(2);
//    adj[2].push_back(1);
//    adj[1].push_back(3);
//    adj[3].push_back(1);
//    adj[2].push_back(4);
//    adj[4].push_back(2);
//    adj[2].push_back(5);
//    adj[5].push_back(2);
// 
// 
//    /* maxCount will have diameter of tree */
//    cout << "Diameter of the given tree is "
//        << diameter(adj, n) << endl;
//    return 0;
//}
  
vector<vector<int>> comb(int N, int K)
{
    std::string bitmask(K, 1); // K leading 1's
    bitmask.resize(N, 0); // N-K trailing 0's
    vector<vector<int>> ret;
 
    // print integers and permute bitmask
    do {
        vector<int> now;
        for (int i = 0; i < N; ++i) // [0..N-1] integers
        {
            if (bitmask[i]) now.push_back(i);
        }
        ret.push_back(now);
    } while (std::prev_permutation(bitmask.begin(), bitmask.end()));
    return ret;
}


public:
    vector<int> countSubgraphsForEachDiameter(int n, vector<vector<int>>& edges) {
      vector<int> ret(n-1, 0);
      for (int nedges = 1; nedges < n; nedges++) {
        vector<vector<int>> selected_edges_list = comb(n-1, nedges);
        for (vector<int>& selected_edges: selected_edges_list) {
          set<int> nodes;
          for (int i: selected_edges) {
            nodes.insert(edges[i][0]);
            nodes.insert(edges[i][1]);
          }
          if (nodes.size() != nedges + 1) continue;
          list<int>* adj = new list<int>[n + 1];
          for (int i: selected_edges) {
            adj[edges[i][0]].push_back(edges[i][1]);
            adj[edges[i][1]].push_back(edges[i][0]);
          }
          int d = diameter(adj, n, *nodes.begin());
          //cout << d << endl;
          ret[d-2]++;
        }
      }
      return ret;
    }
};
125890