Count Subtrees With Max Distance Between Cities - Solution & Explanation
Problem Statement
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- All pairs
(ui, vi)are distinct.
Approach Overview
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 1: Using Bitmask and Floyd-Warshall Algorithm
This approach uses a combination of bit masking to enumerate all possible subtrees and Floyd-Warshall to compute all-pairs shortest paths for each subset.
The code iterates over all subsets of nodes using a bitmask approach for subsets, and then leverages the Floyd-Warshall algorithm to find the shortest paths between all node pairs. It finds the maximum distance between any pair of nodes in each subset and updates the answer array accordingly.
Code
Python
Complexity
The time complexity is O(2^n * n^3) due to iterating over all subsets and using the Floyd-Warshall for each pair. The space complexity is O(n^2) due to the adjacency matrix used in Floyd-Warshall.
Approach 2: Dynamic Programming with Depth First Search (DFS)
This approach uses dynamic programming techniques paired with DFS to calculate the maximum distances within each subtree.
In this solution, we use DFS to ensure that each subset of nodes forms a connected subtree. Then, through dynamic programming, we calculate and track the maximum distance within the subtree by iterating over possible node pairs.
Code
Java
Complexity
The time complexity is O(2^n * n^2) due to working with dfs and bitmasking over subsets. The space complexity is O(n), primarily due to the storage required for visited states and the dynamic programming table.
Approach 3: Dynamic Programming Approach
The dynamic programming approach is ideal for problems that can be broken down into overlapping sub-problems and that exhibit optimal substructure. By saving solutions to these sub-problems, the algorithm avoids redundant work, significantly cutting down on computation time.
This C program calculates the nth Fibonacci number using dynamic programming. We use an array dp to store results of sub-problems, ensuring each number is calculated only once.
Complexity
Time Complexity: O(n)
Space Complexity: O(n) due to the dp array.
Approach 4: Iterative Approach
An iterative approach to problems like Fibonacci is often more space-efficient than recursive approaches because it doesn’t require additional space for recursion stack. This method typically uses a simple loop to compute results.
In this C solution, we iteratively compute Fibonacci numbers using only two variables, thus minimizing space overhead.
Complexity
Time Complexity: O(n)
Space Complexity: O(1) due to constant additional storage.
Approach 5: Default Approach
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Using Bitmask and Floyd-Warshall Algorithm | The time complexity is O(2^n * n^3) due to iterating over all subsets and using the Floyd-Warshall for each pair. The space complexity is O(n^2) due to the adjacency matrix used in Floyd-Warshall. |
| Dynamic Programming with Depth First Search (DFS) | The time complexity is O(2^n * n^2) due to working with dfs and bitmasking over subsets. The space complexity is O(n), primarily due to the storage required for visited states and the dynamic programming table. |
| Dynamic Programming Approach | Time Complexity: O(n) |
| Iterative Approach | Time Complexity: O(n) |
| Default Approach | — |
Detailed Complexity Analysis
| 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 |
Video Solution
花花酱 LeetCode 1617. Count Subtrees With Max Distance Between Cities - 刷题找工作 EP362 • Hua Hua • 2,139 views views
Watch 7 more video solutions →Frequently Asked Questions
Is Count Subtrees With Max Distance Between Cities easy or hard?
Count Subtrees With Max Distance Between Cities Python/Java solution
How to solve Count Subtrees With Max Distance Between Cities in O(n * 2^n)?
What is the best approach for Count Subtrees With Max Distance Between Cities?
Is Count Subtrees With Max Distance Between Cities asked at Google/Amazon/Meta?
What data structure is used in Count Subtrees With Max Distance Between Cities?
What is the time complexity of Count Subtrees With Max Distance Between Cities?
Ready to solve this problem?
Practice Count Subtrees With Max Distance Between Cities with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor