Subtree Descendant Counts

You are given a rooted tree with n nodes labeled 1 to n, where node 1 is the root, described by an array parents of n - 1 integers, where parents[i] is the parent of node i + 2. A parent's label is always smaller than its child's label.

Return an array of n integers where entry i (0-based) is the number of descendants of node i + 1, meaning all nodes in its subtree except itself.

Examples

Example 1

Input: parents = [1,1,2,3]
Output: [4,1,1,0,0]
Explanation: Nodes 2 and 3 are children of node 1; node 4 is a child of node 2; node 5 is a child of node 3. Node 1 has all four other nodes beneath it, nodes 2 and 3 have one descendant each, and nodes 4 and 5 are leaves.

Example 2

Input: parents = []
Output: [0]
Explanation: A single-node tree, so the root has no descendants.