#1617
Count Subtrees With Max Distance Between Cities
expert · 1045 · lc hard +32 · verified · 67.4% accepted · 571 likes · top 74%
Description
There are n cities forming a tree with n-1 edges. A subtree is any connected subset of cities. For each integer d from 1 to n-1, count the subtrees in which the maximum distance between any two member cities equals exactly d. Return an array of n-1 values.
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]
Code
1
2
3