P16943 「LAOI-18」火**印奔行者
题目背景
在某些游戏上只能显示为“火**印奔行者”（尤其是炉石传说！）
题目描述
有一棵无根树，初始时只有节点 $1$。
有 $n - 1$ 次操作，第 $i$ 次操作创建节点 $i + 1$，$i + 1$ 号节点的父亲为读入的 $x_{i + 1}$。
执行完每一次操作后，输出：
任意删去树中的两个节点，并删去所有与这两个节点直接相连的边，剩余部分所形成连通块个数的最大值。
输入格式
第一行一个整数 $n\ (2 \leq n \leq 3 \times 10^6)$。
接下来一行 $n - 1$ 个整数 $x_2,x_3,\cdots,x_n\ (1 \le x_i < i)$。
输出格式
一行 $n - 1$ 个整数表示答案。
说明/提示
**样例 1 解释**
在第 $7$ 次操作后形成的树如上，此时选择删去 $1$、$4$ 节点，以及所有与它们直接相连的边，剩余的连通块数量为 $5$。不存在其他选法能使得剩余的连通块数量更多。
**请使用较快的读入与输出方式**。