<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:
    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:
        edges2 = defaultdict(list) #direct access node edges in O(1) instead of traversing all edges
        for a,b in edges:
            edges2[a].append(b)
            edges2[b].append(a)

        def bfs(root,nodes): #bfs returning max depth and first node on last layer
            level = [root] #bfs-queue
            seen = {root} #dont use again flags
            d = 0 #depth
            while True: #do while
                nextLevel = []
                for node in level: #bfs
                    for other in edges2[node]: #children
                        if nodes[other-1]==True and other not in seen: #children not deleted or used already
                            seen.add(other) #mark as used
                            nextLevel.append(other) #add to next bfs queue
                if nextLevel: #continue
                    d += 1 #next depth reached
                    level = nextLevel #take over children as bfs queue/layer
                else: break #done with bfs
            return level[0],d #first node + depth from root

        seen = set() #dont reuse same combinations
        def rec(nodes=[True for _ in range(n)]): #what dist is left with given connected nodes
            seen.add(str(nodes)) #never eval this combination again
            if sum(nodes)==1: return #deleted to much
            for i,b in enumerate(nodes):
                if b==True: #pick first node left as root
                    root = i+1
                    break
            #double bfs=>max-depth-node yiels max dist
            #also we have both reached nodes and the path between has the distance!
            other,_ = bfs(root,nodes) #first bfs
            _,dist = bfs(other,nodes) #second bfs
            res[dist-1] += 1 #save another subtree got this dist

            for i,b in enumerate(nodes): #try to delete nodes
                if b==True: #this one is left
                    node = i+1 #the node value 1-indexed
                    reaches = 0 #counter
                    for other in edges2[node]: #connected nodes
                        if nodes[other-1]==True: #is not yet deleted
                            reaches += 1 #add as connected node
                    #leafs can get deleted!
                    if reaches==1: #leafs have exactly 1 connection
                        new = list(nodes) #unlinked copy for more readable recursion
                        new[node-1] = False #flip deletable => smaller nodes combination
                        if str(new) not in seen: #this combination is new!
                            rec(new) #get max dist for subset also


        res = [0 for _ in range(1,n)] #counts of max dists from 1 to n-1
        rec() #recursivley use all subtrees
        return res #return counts
20100