Bessie đang giúp Elsie chuẩn bị cho bài kiểm tra từ vựng sắp tới. Các từ được kiểm tra sẽ lấy từ một ngân hàng gồm \(M\) từ phân biệt, trong đó không từ nào trong ngân hàng là tiền tố của một từ khác trong ngân hàng.

Khi ngân hàng còn từ, Bessie sẽ chọn một từ, xóa nó khỏi ngân hàng và đọc cho Elsie từng ký tự từ trái sang phải. Nhiệm vụ của Elsie là báo cho Bessie ngay khi cô có thể xác định duy nhất từ đó; khi ấy Bessie sẽ ngừng đọc.

Bessie đã quyết định đọc các từ trong ngân hàng theo thứ tự \(w_1,w_2,\dots,w_M\). Nếu Elsie trả lời nhanh nhất có thể, Bessie sẽ đọc bao nhiêu ký tự của mỗi từ?

Các từ được cho dưới dạng nén. Trước tiên, ta định nghĩa \(N+1\) (\(1\le N\le 10^6\)) từ phân biệt, rồi ngân hàng từ sẽ gồm tất cả những từ không phải là tiền tố của một từ khác. Các từ được định nghĩa như sau:

• Ban đầu, từ thứ \(0\) là xâu rỗng.
• Sau đó, với mỗi \(1\le i\le N\), từ thứ \(i\) bằng từ thứ \(p_i\) cộng thêm một ký tự ở cuối (\(0\le p_i<i\)). Các ký tự được chọn sao cho cả \(N+1\) từ đều phân biệt.

Dữ liệu vào

Dòng đầu tiên chứa \(N\), trong đó \(N+1\) là số từ được cho dưới dạng nén.

Dòng tiếp theo chứa \(p_1,p_2,\dots,p_N\), trong đó \(p_i\) biểu thị rằng từ thứ \(i\) được tạo bằng cách lấy từ thứ \(p_i\) rồi thêm một ký tự vào cuối.

Gọi \(M\) là số từ không phải tiền tố của bất kỳ từ nào khác. \(M\) dòng tiếp theo chứa lần lượt \(w_1,w_2,\dots,w_M\), nghĩa là từ thứ \(w_i\) sẽ được đọc ở vị trí thứ \(i\). Đảm bảo các từ được đọc tạo thành một hoán vị của các từ trong ngân hàng.

Dữ liệu ra

In ra \(M\) dòng, trong đó dòng thứ \(i\) chứa số ký tự của từ thứ \(i\) trong thứ tự đọc mà Bessie đọc.

Ví dụ

5
0 1 2 3 4
5

0

4
0 0 1 1
4
3
2

2
1
0

4
0 0 1 1
2
3
4

1
2
0

Phân nhóm

• Dữ liệu 4–5: Không từ nào có độ dài lớn hơn \(20\).
• Dữ liệu 6–10: Tổng độ dài của tất cả các từ trong ngân hàng không vượt quá \(10^7\).
• Dữ liệu 11–18: Không có ràng buộc bổ sung.

Nguồn

USACO 2025 February Contest, Silver — Vocabulary Quiz. Tác giả: Benjamin Qi.

https://usaco.org/index.php?page=viewproblem2&cpid=1495