Đường kính cây khi thêm lá
Points
65
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Đề 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$.
Community Discussion