862. Subtrees by Diameter
A cave system has n chambers numbered 0 to n - 1, linked by n - 1 tunnels (edges[i] = [a, b]) so that every chamber can reach every other. A section is any non-empty set of chambers in which every two chambers are connected using only tunnels between chambers of the set. The span of a section is the largest number of tunnels on the route between two of its chambers (a single chamber has span 0).
Return an array res of length n - 1 where res[d - 1] is the number of sections whose span is exactly d, for d = 1, ..., n - 1. Two sections differ if their sets of chambers differ.
Example 1
- Input:
- n = 4, edges = [[0,1],[1,2],[2,3]]
- Output:
- [3,2,1]
- Explanation:
On the line 0-1-2-3 there are 3 sections of span 1 (single tunnels), 2 of span 2 ({0,1,2} and {1,2,3}) and 1 of span 3 (all chambers).
Example 2
- Input:
- n = 4, edges = [[0,1],[0,2],[0,3]]
- Output:
- [3,4,0]
- Explanation:
Chamber 0 touches the other three: 3 sections of span 1, and 4 of span 2 (0 with any two or all three of its neighbours); no section has span 3.
Constraints
- 2 ≤ n ≤ 30
edges.length == n - 1, 0 ≤ a, b < n and the tunnels form a tree- Every count fits in a signed 32-bit integer
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 400 msC++ 100 msJava 200 msJavaScript 200 msTypeScript 200 ms
Expected complexity
- Time
- O(n^3 * deg)
- Space
- O(n^2)