Đếm Cấp Dưới Xuất Sắc

Điểm: 1,00 (OI)

Giới hạn thời gian: 4.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Công ty của bò có cấu trúc phân cấp dạng cây có gốc, với bò số $1$ là chủ tịch (gốc). Mỗi con bò có một chỉ số năng lực riêng biệt. Nhiệm vụ của bạn là: với mỗi con bò, đếm xem có bao nhiêu cấp dưới (tức là con cháu trong cây) có chỉ số năng lực cao hơn nó.

Một con bò $v$ là cấp dưới của con bò $u$ nếu $u$ nằm trên đường đi từ $v$ đến gốc (tức $u$ là tổ tiên thực sự của $v$ ).

Dữ liệu vào

Dòng $1$ : số nguyên $N$ — số lượng bò trong công ty.
$N$ dòng tiếp theo: dòng $i$ chứa chỉ số năng lực $p_{i}$ của bò $i$ (các giá trị phân biệt nhau).
$N - 1$ dòng tiếp theo: dòng $i$ chứa chỉ số của người quản lý (cha) của bò $i + 1$ trong cây.

Dữ liệu ra

$N$ dòng, dòng thứ $i$ chứa số lượng cấp dưới của bò $i$ có chỉ số năng lực cao hơn bò $i$ .

Ràng buộc

$1 \leq N \leq 100 000$
$1 \leq p_{i} \leq 10^{9}$ , các $p_{i}$ phân biệt nhau.

Ví dụ

Input	Output	Giải thích
5 804289384 846930887 681692778 714636916 957747794 1 1 2 3	2 0 1 0 0	Cây: bò 1 là gốc; con của bò 1 là bò 2 và bò 3; con của bò 2 là bò 4; con của bò 3 là bò 5. Bò 1 (năng lực 804289384): cấp dưới gồm bò 2 (846930887 > 804289384) và bò 5 (957747794 > 804289384) → 2. Bò 2 (846930887): cấp dưới là bò 4 (714636916 < 846930887) → 0. Bò 3 (681692778): cấp dưới là bò 5 (957747794 > 681692778) → 1. Bò 4, bò 5 không có cấp dưới → 0.

Ghi chú

Trong phần dữ liệu vào, $N - 1$ dòng cuối cùng mô tả cha của bò $2, 3, \dots, N$ lần lượt. Cây luôn có gốc là bò $1$ .

Bình luận

Không có bình luận tại thời điểm này.