U463272 Tree 2-Coloring

忙碌的阿狸正在装饰一棵圣诞树，但他对颜色有一些奇怪的偏好。 

考虑用红、绿两种颜色为一棵树的顶点着色。 在着色中，如果绿色顶点的连通分量最多有两个红色顶点相邻，则称该分量为冷分量。对于一棵树 $t$，设 $f(t)$ 是 $t$ 的任何着色中冷色分量的最大数目。 有一棵树$t$，最初只包含一个顶点，记为顶点 $1$。执行 $n$ 次查询；在第 $i$ 次查询中，添加一个叶顶点，将其附加到顶点 $a_i$ 上。 你需要在每次查询后输出 $f(t)$。

**注意：本题采用多组数据。** 第一行一个正整数：$T$，表示数据组数； 接下来 $T$ 组数据，对于每一组数据： 第一行 $1$ 个正整数：$n$，表示有 $n$ 个添加点； 第二行 $n$ 个正整数：$a_i$，表示第 $i+1$ 个点的父亲；

对于每组数据： 一行 $n$ 个数：$f_i(t)$。

**【数据范围】** 对于所有测试数据保证：$T\le 10^5,\sum n\le 2\times 10^5,1\le a_i< i$。 | 测试点编号 | $\sum n\leq$ | 特殊性质或约束 | | :----------: | :----------: | :----------: | | $1,2$ | $20$ | \ | | $3,4,5,6$ | $2000$ | \ | | $7,8$ | $2\times 10^5$ | $a_i=1$ | | $9,10$ | $2\times 10^5$ | $a_i=i-1$ | | $11,12$ | $2\times 10^5$ | $a_i$ 随机生成 | | $13,14,15,16,17,18,19,20$ | $2\times 10^5$ | \ |