Đường kính cây khi thêm lá

General
Points
65
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions
Đề bài

Ban đầu cây chỉ có duy nhất một đỉnh là đỉnh $1$. Thực hiện $Q$ bước: ở bước thứ $i$ ($1 \le i \le Q$), thêm đỉnh mới $i + 1$ nối bằng một cạnh độ dài $1$ với đỉnh $p_i$ ($1 \le p_i \le i$). Sau mỗi bước, hãy in ra đường kính hiện tại của cây (độ dài đường đi đơn dài nhất giữa hai đỉnh bất kỳ).

Dữ liệu vào

Dòng đầu chứa số nguyên $Q$. $Q$ dòng tiếp theo, dòng thứ $i$ chứa số nguyên $p_i$.

Dữ liệu ra

Gồm $Q$ dòng, dòng thứ $i$ là đường kính của cây sau bước thứ $i$.

Ví dụ
Input Output
4
1
1
2
3
1
2
3
4
Giới hạn

$1 \le Q \le 10^5$, $1 \le p_i \le i$.

Draft saved