Trees and recursion 0/36

Lesson 4 of 5

General trees

Root a tree from an edge list, push values down or combine them up: subtree sizes, the diameter, centres and distance sums for every root.

5,717 words · 26 min read

Part 1 of 10 General trees

Trees with any number of children

In a binary tree every node has at most two children, kept in the fields left and right. Many trees have no such limit: a manager can have any number of people reporting to them, and a folder can hold any number of folders. A tree like this is called a general tree, and each of its nodes keeps a list of its children in place of the two fields.

The words root, parent, child, leaf and subtree mean the same as in a binary tree. The first problem uses them for the staff of a company.

A company has nn employees, numbered 1 to nn. Employee 1 is the general director, and every other employee has exactly one direct boss. The subordinates of an employee are everyone below them: the people who report to them, the people who report to those, and so on.

The first input line holds nn, and the second holds the direct bosses of employees 2,3,…,n2, 3, \dots, n. Print the number of subordinates of each employee, from 1 to nn.

Constraints

  • 1≤n≤2⋅1051 \le n \le 2 \cdot 10^5

Sample · Input

5
1 1 2 3

Output

4 1 1 0 0

In the sample, employees 2 and 3 report to employee 1, employee 4 reports to 2 and employee 5 reports to 3. The company is a tree with employee 1 as the root, and the boss of an employee is that node's parent:

14 below21 below31 below40 below50 below

The subtree of an employee is that employee together with everyone below them. The subordinates are the other nodes of the subtree, so each answer is the size of a subtree minus 1. The subtree of employee 1 holds all five employees, and 5−1=45 - 1 = 4.

We could count every subtree separately, by visiting everyone below each employee in turn. That visits the same people many times: employee 4 is visited for employee 2 and again for employee 1. It is slowest when the company is a chain, in which each employee is the boss of the next. With 200,000 employees, the count for employee 1 visits 199,999 people, the count for employee 2 visits 199,998, and so on:

199,999+199,998+⋯+1=199,999×200,0002=19,999,900,000 visits199{,}999 + 199{,}998 + \dots + 1 = \frac{199{,}999 \times 200{,}000}{2} = 19{,}999{,}900{,}000 \text{ visits}

At roughly 10810^8 simple operations a second, that is about 200 seconds, and the time limit is one second.

The sizes can be computed without the repeated visits, because a subtree is its top node together with the subtrees of that node's children. Its size is therefore 1, for the top node, plus the sizes of the children's subtrees. Once the children's sizes are known, their parent's size takes one addition per child, so each size is worked out once and then used once, by the parent. In the sample:

size[4]=1size[5]=1size[2]=1+size[4]=2size[3]=1+size[5]=2size[1]=1+size[2]+size[3]=5\begin{aligned} \texttt{size}[4] &= 1 \\ \texttt{size}[5] &= 1 \\ \texttt{size}[2] &= 1 + \texttt{size}[4] = 2 \\ \texttt{size}[3] &= 1 + \texttt{size}[5] = 2 \\ \texttt{size}[1] &= 1 + \texttt{size}[2] + \texttt{size}[3] = 5 \end{aligned}

In code this has the shape of the recursive height function of a binary tree, with a loop over the children in place of the two calls and a sum in place of the larger of two heights. The program first builds the list of children of every employee from the line of bosses:

Sign up to run
input = sys.stdin.readline

def subtree_size(v):
    size[v] = 1                         # the employee
    for child in children[v]:
        size[v] += subtree_size(child)  # the child's whole subtree
    return size[v]

n = int(input())
bosses = list(map(int, input().split()))
children = [[] for _ in range(n + 1)]
for employee, boss in enumerate(bosses, 2):
    children[boss].append(employee)
size = [0] * (n + 1)
subtree_size(1)
print(*(size[v] - 1 for v in range(1, n + 1)))

The first two lines replace input with a faster way to read a line, which large inputs need. The lists have n + 1 entries so that employee v can use entry v. enumerate(bosses, 2) numbers the bosses from 2, because the first number on the line is the boss of employee 2.

A leaf has an empty list of children, so its loop does nothing and its size stays 1. That is the base case, and the function needs no test for a missing child. The function is called once for every employee, and its loops run n−1n - 1 times in total, once for every employee who has a boss, so the program takes O(n)O(n) time.

The program is not ready to submit, though. In a chain of 200,000 employees the calls nest 200,000 deep, and Python stops with an error after about 1,000 nested calls. The third part of this lesson replaces the recursion with a loop.