Sơ đồ nhân sự phân cấp

Bối cảnh và bài toán

Một tổ chức có n nhân sự được bố trí theo một cây quản lý có gốc. Nhân sự số 1 là người đứng đầu; mỗi nhân sự còn lại có đúng một quản lý trực tiếp. Hệ thống báo cáo cần biết, với từng người, có bao nhiêu nhân sự nằm trong toàn bộ nhánh quản lý bên dưới họ, không chỉ những người báo cáo trực tiếp.

Yêu cầu

Với mỗi nhân sự từ 1 đến n, hãy tính số hậu duệ của họ trong cây quản lý.

Input

• Dòng 1 chứa n.
• Dòng 2 chứa n-1 số p_2, p_3, ..., p_n, trong đó p_i là quản lý trực tiếp của nhân sự i.

Output

In n số; số thứ i là số nhân sự thuộc toàn bộ cây con bên dưới nhân sự i.

Ràng buộc

• 1 <= n <= 2 * 10^5
• 1 <= p_i < i sau khi chuẩn hóa dữ liệu theo thứ tự cấp phát ID.

Chấm điểm

Ví dụ 1

Input

5
1 1 2 3

Output

4 1 1 0 0

Giải thích. Nhân sự 1 quản lý toàn bộ 4 người còn lại; nhân sự 2 và 3 mỗi người có một hậu duệ.

Ví dụ 2

Input

6
1 1 1 4 4

Output

5 0 0 2 0 0

Giải thích. Nút 4 có hai hậu duệ là 5 và 6.

Thông tin bài tập

Nguồn: Phỏng theo CSES Problem Set – Subordinates.