{x}
blog image

Count Subtrees With Max Distance Between Cities

There are n cities numbered from 1 to n. You are given an array edges of size n-1, where edges[i] = [ui, vi] represents a bidirectional edge between cities ui and vi. There exists a unique path between each pair of cities. In other words, the cities form a tree.

A subtree 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.

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

Return an array of size n-1 where the dth element (1-indexed) is the number of subtrees in which the maximum distance between any two cities is equal to d.

Notice that the distance between the two cities is the number of edges in the path between them.

 

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.

Solution Explanation for LeetCode 1617: Count Subtrees With Max Distance Between Cities

This problem asks to find, for each distance d from 1 to n-1, the number of subtrees where the maximum distance between any two nodes is d. The input is a tree represented by n nodes and n-1 edges. The solution leverages bit manipulation and depth-first search (DFS) or breadth-first search (BFS) to efficiently explore the subtrees.

Core Idea:

The key is to iterate through all possible subtrees of the given tree. Since the number of nodes (n) is limited (up to 15), we can represent each subtree as a bitmask of size n. A bit set to 1 indicates that the corresponding node belongs to the subtree. Then, for each subtree, we calculate the maximum distance between any two nodes within that subtree.

Algorithm:

  1. Graph Representation: Construct an adjacency list representation of the input tree from the given edges.

  2. Iterate through Subtrees: Iterate through all possible subsets of nodes (subtrees) using bitmasks. A bitmask of size n is used, where each bit represents a node. A bit set to 1 means the node is included in the current subtree. We skip masks that are empty or represent only a single node.

  3. DFS/BFS for Maximum Distance: For each valid bitmask (subtree):

    • Perform a DFS or BFS starting from an arbitrary node in the subtree. This traversal only considers edges connecting nodes present in the current subtree.
    • Track the farthest node reached and the distance to that node. This gives one endpoint of the maximum diameter.
    • Then, repeat the DFS/BFS starting from this farthest node. This traversal will find the other end of the diameter and the maximum distance, which is the diameter of the subtree.

  4. Counting Subtrees: Increment the count in the ans array at index d-1 (since array is 0-indexed, and d is 1-indexed in the problem description), where d is the maximum distance found for the current subtree.

Time Complexity Analysis:

  • Iterating through all possible subtrees takes O(2n) time.
  • For each subtree, DFS or BFS takes O(n) time in the worst case (a linear time algorithm on a tree).
  • Therefore, the overall time complexity is O(n * 2n). The exponential factor dominates, making it suitable only for small values of n (as specified in the problem constraints).

Space Complexity Analysis:

  • The adjacency list takes O(n) space.
  • The ans array takes O(n) space.
  • The call stack for DFS or the queue for BFS takes O(n) space in the worst case.
  • The overall space complexity is O(n).

Code Examples (Python):

Both Solution 1 and Solution 2 are provided above in multiple languages; they differ slightly in how they perform the BFS/DFS to find the maximum distance within a subtree. Solution 1 uses a recursive DFS, while Solution 2 utilizes iterative BFS. The time and space complexity analysis remains the same for both. Choose whichever style you find more readable and easier to understand.

Note: The numberOfLeadingZeros function in TypeScript is a helper function to efficiently find the index of the most significant bit (MSB), which is needed to find a starting node for DFS/BFS in the subtree represented by the bitmask. Similar optimized functions (e.g., using __builtin_clz in C++ or bits.Len in Go) are used in the other code examples to achieve the same.