Mô tả bài toán

Một công ty gồm $n$ thành viên có mã nhân viên là $1, 2, \dots, n$. Thành viên $1$ là sếp, và mỗi thành viên $i$ khác ($2 \le i \le n$) đều có một cấp trên trực tiếp là $f_i$ ($1 \le f_i < i$). Cấu trúc công ty tạo thành một cây có gốc với thành viên $1$ là gốc.

Trong công ty này, thành viên $a$ quen biết thành viên $b$ khi và chỉ khi thỏa mãn ít nhất một trong các điều kiện sau:

• $a = b$.
• $b$ là tổ tiên của $a$. Nói cách khác, tồn tại một dãy $u_1, u_2, \dots, u_k$ ($2 \le k$) sao cho $u_1 = a$, $u_k = b$, và $u_i = f_{u_{i-1}}$ với mọi $2 \le i \le k$.
• $b$ là con trực tiếp của $a$ ($b$ là cấp dưới trực tiếp của $a$). Nói cách khác, $f_b = a$.

Lưu ý rằng mối quan hệ quen biết không nhất thiết có tính đối xứng; $a$ quen biết $b$ không có nghĩa là $b$ quen biết $a$.

Bây giờ, các thành viên đang chơi một trò chơi. Trong mỗi vòng, một thành viên cụ thể $m$ đóng vai trò là người đoán, và một thành viên khác $p$ là mục tiêu. Dữ liệu đảm bảo rằng $p$ là một thành viên mà $m$ không quen biết.

Để xác định $p$, $m$ đặt một chuỗi các câu hỏi. Với mỗi câu hỏi, $m$ chọn một mã nhân viên $x$ và hỏi: "$p$ có quen biết thành viên $x$ không?" Thành viên $p$ luôn trả lời trung thực. Ngoài ra, nếu $x = p$, $p$ sẽ đặc biệt tiết lộ rằng mình chính là thành viên $x$, và trò chơi kết thúc ngay tại thời điểm đó.

Mỗi câu hỏi tốn một chi phí di chuyển dựa trên cây công ty. Nếu câu hỏi thứ $i$ liên quan đến thành viên $x_i$, chi phí của câu hỏi đó là $dis(x_{i-1}, x_i)$, trong đó $dis(a, b)$ là số cạnh trên đường đi duy nhất giữa $a$ và $b$ trong cây. Đối với câu hỏi đầu tiên ($i = 1$), chi phí là $dis(m, x_1)$.

Thành viên $m$ cực kỳ thông minh và sử dụng chiến lược tối ưu để cực tiểu hóa tổng chi phí cần thiết nhằm đảm bảo hoàn thành trò chơi trong trường hợp xấu nhất. Nhiệm vụ của bạn là tính chi phí trường hợp xấu nhất nhỏ nhất này cho mọi người đoán có thể $m \in \{1, 2, \dots, n\}$.

Nếu một thành viên $m$ đã quen biết tất cả mọi người trong công ty, câu trả lời cho $m$ đó là $0$.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa một số nguyên $n$ ($1 \le n \le 10^5$), biểu thị tổng số thành viên trong công ty.

Dòng thứ hai chứa $n - 1$ số nguyên, biểu thị $f_2, f_3, \dots, f_n$. Thỏa mãn $1 \le f_i < i$.

Kết quả

In ra một dòng duy nhất chứa $n$ số nguyên, biểu thị câu trả lời cho các trường hợp $m = 1, m = 2, \dots, m = n$. Các số nguyên được ngăn cách bởi dấu cách.

Ví dụ

Dữ liệu vào 1

3
1 1

Kết quả 1

0 2 2

Dữ liệu vào 2

5
1 1 3 2

Kết quả 2

4 3 3 4 4

Dữ liệu vào 3

6
1 1 2 2 3

Kết quả 3

4 3 5 4 4 6

Ghi chú

Để giải thích trường hợp $m = 4$ trong ví dụ 3: Đầu tiên, như thể hiện trong sơ đồ, thành viên $m$ không quen biết các thành viên $\{3, 5, 6\}$. Một chiến lược tối ưu khả dĩ là trước tiên hỏi xem $p$ có quen biết thành viên $2$ hay không, tốn chi phí $1$. Nếu có, điều đó cho thấy $p = 5$, và bước tiếp theo là hỏi về thành viên $5$ để kết thúc trò chơi, với tổng chi phí là $2$. Ngược lại, tiếp tục hỏi xem $p$ có quen biết thành viên $3$ hay không, tốn chi phí $2$. Nếu $p = 3$, trò chơi kết thúc với tổng chi phí là $3$. Ngược lại, điều đó cho thấy $p = 6$, và bước tiếp theo tốn chi phí $1$ để hỏi về thành viên $6$, kết thúc trò chơi với tổng chi phí là $4$. Do đó, chiến lược này đòi hỏi chi phí trong trường hợp xấu nhất là $4$. Có thể chứng minh rằng không có chiến lược nào khác có thể giảm chi phí truy vấn trong trường hợp xấu nhất xuống thấp hơn nữa.