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.The key observation is that the number of cities n is small (≤ 15), which allows us to enumerate all possible subsets of nodes using bitmasks. For each subset, we check whether it forms a valid subtree (connected and containing exactly k-1 edges for k nodes). If valid, we compute the maximum distance (diameter) between any two cities in that subset.
A common strategy is to use bitmask enumeration to generate all subsets, then perform BFS/DFS restricted to nodes in the subset to verify connectivity and compute the diameter. The diameter can be found using the classic two-pass BFS technique: start from any node to find the farthest node, then run BFS again from that node to get the maximum distance.
For every valid subtree, increment the counter corresponding to its diameter. Although the number of subsets is 2^n, the small constraint keeps the solution efficient. Careful use of adjacency lists and bitmask checks keeps the implementation manageable.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Bitmask Enumeration + BFS Diameter | O(2^n * n^2) | O(n^2) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
Iterate through every possible subtree by doing a bitmask on which vertices to include. How can you determine if a subtree is valid (all vertices are connected)?
To determine connectivity, count the number of reachable vertices starting from any included vertex and only traveling on edges connecting 2 vertices in the subtree. The count should be the same as the number of 1s in the bitmask.
The diameter is basically the maximum distance between any two nodes. Root the tree at a vertex. The answer is the max of the heights of the two largest subtrees or the longest diameter in any of the subtrees.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this type of problem reflects advanced tree and enumeration techniques often discussed in top tech interviews. It tests understanding of bitmasking, graph traversal, and tree diameter concepts, which are common in high-level coding rounds.
An adjacency list is typically used to represent the tree efficiently. Bitmasks help represent subsets of nodes, while BFS or DFS traversal is used to verify connectivity and compute the diameter within each subset.
The common approach is to enumerate all subsets of nodes using bitmasks because the number of cities is small (≤15). For each subset, check if it forms a connected subtree and compute its diameter using BFS or DFS. The counts of diameters are then aggregated for the final result.
Bitmask enumeration works well because the number of nodes is small. It allows efficient generation of all possible subsets and quick checks to see whether a node belongs to the current subset during traversal.