Kiểm Tra Từ Vựng

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.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

Bessie giúp Elsie ôn thi từ vựng. Bộ từ vựng gồm $M$ từ phân biệt, không từ nào là tiền tố của từ khác.

Các từ được xây dựng theo cấu trúc cây: từ 0 là xâu rỗng, từ $i$ ( $1 \leq i \leq N$ ) được tạo bằng cách nối thêm một ký tự vào từ $p_{i}$ . Bộ từ vựng chỉ gồm các từ là lá trong cây (không phải tiền tố của từ nào khác).

Bessie đọc lần lượt từng từ, mỗi từ đọc từng ký tự một từ trái sang phải. Elsie phải nhận diện từ đó sớm nhất có thể. Sau khi Elsie nhận ra một từ, từ đó (và mọi từ trung gian trên đường từ gốc đến nó) bị loại khỏi cây xét.

Với mỗi từ trong thứ tự đọc, hãy tính số ký tự Bessie cần đọc.

Dữ liệu vào

Dòng 1: Số nguyên $N$ ( $1 \leq N \leq 2 \times 10^{6}$ )
Dòng 2: $N$ số nguyên $p_{1}, p_{2}, \dots, p_{N}$ ( $0 \leq p_{i} < i$ )
$M$ dòng tiếp theo: Mỗi dòng chứa chỉ số của từ cần đọc (theo thứ tự)

Dữ liệu ra

$M$ dòng, mỗi dòng là số ký tự Bessie cần đọc cho từ tương ứng.

Ràng buộc

$1 \leq N \leq 2 \times 10^{6}$

Ví dụ

Input	Output	Giải thích
5 0 1 2 3 4 5	0	Cây là đường thẳng, chỉ có từ 5 trong bộ. Elsie biết ngay từ đó mà không cần đọc ký tự nào.
4 0 0 1 1 4 3 2	2 1 0	Ba từ trong bộ: từ 2, 3, 4. Đọc từ 4 cần 2 ký tự (phân biệt với từ 3). Đọc từ 3 cần 1 ký tự. Đọc từ 2 cần 0 ký tự (chỉ còn lại một từ).

Bình luận

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