Count Subtrees With Max Distance Between Cities
01 · Problem
There are n cities numbered 1 to n, connected by n - 1 bidirectional roads so that the cities form a tree. edges[i] = [u_i, v_i] is a road between u_i and v_i.
A subtree here is any non-empty subset of cities that is connected using only roads between cities in the subset. Two subtrees are different if their sets of cities differ. The diameter of a subtree is the largest number of roads on the path between any two of its cities.
Return an array of length n - 1 whose d-th entry (1-indexed, so index d - 1) is the number of subtrees whose diameter is exactly d. Single-city subtrees have diameter 0 and are not counted.
02 · Examples
n = 4, edges = [[1,2],[2,3],[2,4]]
[3,4,0]
The connected subsets of size 2 ({1,2}, {2,3}, {2,4}) have diameter 1. The subsets {1,2,3}, {1,2,4}, {2,3,4} and {1,2,3,4} have diameter 2. No subset has diameter 3.
n = 2, edges = [[1,2]]
[1]
The only connected subset with at least two cities is {1,2}, with diameter 1.
n = 3, edges = [[1,2],[2,3]]
[2,1]
{1,2} and {2,3} have diameter 1, and {1,2,3} has diameter 2.
03 · Constraints
- 012 <= n <= 15
- 02edges.length == n - 1
- 031 <= u_i, v_i <= n and u_i != v_i
- 04The edges form a valid tree.
04 · Optimal complexity
- Time
- O(2^n * n^2)
- Space
- O(n^2)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.