Watch 8 video solutions for Count Subtrees With Max Distance Between Cities, a hard level problem involving Dynamic Programming, Bit Manipulation, Tree. This walkthrough by Hua Hua has 2,134 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 15edges.length == n-1edges[i].length == 21 <= ui, vi <= n(ui, vi) are distinct.Problem Overview: You are given n cities connected as a tree. For every possible connected subset of cities (a subtree), compute its diameter—the maximum distance between any two cities inside that subset. The task is to count how many subtrees have diameter d for each 1 ≤ d < n.
Approach 1: Bitmask Enumeration + Floyd-Warshall (O(n^3 * 2^n) time, O(n^2) space)
Enumerate every subset of cities using a bitmask. For each subset, verify that it forms a connected subtree by counting edges or running a DFS. Precompute all-pairs shortest paths with the Floyd-Warshall algorithm so distance queries are constant time. Once the subset is validated, iterate over every pair of nodes inside the mask and compute the maximum pairwise distance to get the diameter. This method is straightforward and works because n ≤ 15, making 2^n manageable.
Approach 2: Dynamic Programming with DFS (O(n * 2^n) time, O(n * 2^n) space)
This approach still enumerates subsets but avoids repeated distance calculations. For each subset, run a DFS restricted to nodes inside the mask. Track the farthest node to compute the diameter using the classic two-DFS tree diameter trick. The DP component caches valid subtree states so connectivity checks are efficient. Since each subset processes only its internal edges, the complexity improves significantly compared to recomputing all-pairs distances.
Approach 3: Dynamic Programming on Subsets (O(n * 2^n) time, O(2^n) space)
Instead of recomputing properties from scratch, build results incrementally. Maintain DP information about the farthest node distances for subsets while expanding masks. If adding a node preserves connectivity, update the maximum path length using distances to existing nodes. This avoids repeated DFS traversals and keeps computations localized to the subset transition. This version is common in optimized competitive programming solutions involving bitmask subset DP.
Approach 4: Iterative Enumeration with Tree Properties (O(n * 2^n) time, O(n) space)
Because the original graph is a tree, any valid subtree with k nodes must contain exactly k-1 edges. Iterate through subsets, count included edges, and reject masks that violate this property. Once a mask represents a tree, compute its diameter using two DFS passes restricted to the nodes in the mask. This approach is simple and avoids heavy preprocessing while still leveraging tree structure.
Recommended for interviews: The subset enumeration combined with DFS diameter computation is the expected solution. It demonstrates understanding of tree diameter algorithms plus subset generation using bit manipulation. Starting with brute-force subset enumeration shows reasoning about constraints, while optimizing with DP or efficient DFS demonstrates strong algorithmic thinking.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Bitmask + Floyd-Warshall | O(n^3 * 2^n) | O(n^2) | Simplest implementation when precomputing all pair distances is acceptable |
| DP with DFS Diameter | O(n * 2^n) | O(n * 2^n) | Efficient enumeration with cached connectivity checks |
| Subset Dynamic Programming | O(n * 2^n) | O(2^n) | Best for optimized competitive programming solutions using bitmask transitions |
| Iterative Subset + DFS | O(n * 2^n) | O(n) | Interview-friendly approach leveraging tree diameter via two DFS passes |