# Problem

1617. Count Subtrees With Max Distance Between Cities

# Explanation

## bit manipulation to traverse all the subsets

It only have 15 nodes, if we use bit manipulation, we can list all the possible subset of the 15 nodes by traverse from

0 to 2¹⁵

The trick is named bit manipulation

For each number, if the bit value is 1, it mean the subset contains a node.

For example, A, B, C, D, we will have

0000 →{}

0001 →{D}

0010 →{C}

0011 →{C, D}

1111 →{A,B,C,D}

## Check whether a subset is a Tree

For each subset, it may not be a tree. For example, if we have AB connected and CD connected. Then A and C can not generate a Tree. Actually, A and C will be a forest. A way to check whether a subset is a Tree is: traverse the graph from any node, if it is a tree, then, the traverse process will collect all the nodes. If not, the traverse process will be interrupted during the process and some nodes will not be seen or visited.

We can check whether len(seen)== len(nodes)

## If it is a tree, get the diameter.

This is a standard problem and we can use two BFS to solve the problem. For more details see my previous article.

# Summary

Main steps:

• traverse all possible subsets
• for each subset, check whether it is a tree. We can use DFS or BFS, since the diameter of the tree part is using BFS, I am also using BFS here
• Using two BFS to get the diameter of a tree if the graph is a tree.

# Code

`class Solution:    # return whehter the graph is a tree, the last node visited by BFS    # and the max depth of the tree    def bfs(self, node, graph):        Q = collections.deque([(node, 0)])        last_node = None        max_depth = 0        seen = {node}        while Q:            node, depth = Q.popleft()            last_node = node            max_depth = depth            for neighbor in graph[node]:                if neighbor not in seen:                    seen.add(neighbor)                    Q.append((neighbor, depth + 1))        is_tree = len(seen) == len(graph)        return is_tree, last_node, max_depth        def find_diameter(self, graph):        nodes = list(graph.keys())        is_tree, last_node , _ = self.bfs(nodes, graph)        if not is_tree:return -1        _, _, max_depth = self.bfs(last_node, graph)        return max_depth        def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:        graph = collections.defaultdict(set)        for a, b in edges:            graph[a].add(b)            graph[b].add(a)        res = collections.defaultdict(int)                for k in range(1, 1<<n):            nodes = set()            for node in range(n):                if (1<<node) & k:                    nodes.add(node+1)            if len(nodes)==1:continue            new_graph = collections.defaultdict(set)            for node in nodes:                new_graph[node] = graph[node] & nodes                if not new_graph[node]:break            else:                diameter = self.find_diameter(new_graph)                res[diameter] += 1        return [res[diameter] for diameter in range(1,n)]`