解题思路

给定一棵以 1 为根的树（房间 1…n）。除了根以外，每个结点都属于某个父亲的“儿子集合”。传播规则为：

1. 每个时刻，对每个父亲 k，若其儿子中“至少有 1 个知道且至少有 1 个不知道”，则该父亲本时刻恰好再让 1 个儿子知道（同一父亲本时刻最多+1）。
2. 每个时刻，小明还能额外指定 1 个任意房间让其知道。

注意：根结点 1 不在任何“儿子集合”中，因此根只能靠小明点名才能知道。

将问题转化：

题目内容

小红在片区宣传部入职了！国家运动员最近取得了佳绩，小红急需将这个好消息告诉给自己负责的片区的所有居民，让大家受到鼓舞。

这个片区的结构很有意思，呈现一种神奇的树状结构。一共有 $n$ 间房屋，每间房屋住了一位居民，编号分别为 $1,2,…,n$ ，其中编号为 $1$ 的房屋是这个树状结构的根，除了这个房间外的其他房间 $i$ ，均有一个通过向上楼梯连接的房间 $p_i$ 。巧妙的是，如果某些房间通过户上楼梯连接的房间是相同的房间(即它们的 $p_i$ 相同时，假设均为 $k$ ，也即图论中的拥有相同父亲节点时)，这些房间的居民可以很方便的相互通信，这些房间也被称为 $k$ 的儿子房间。

而小红从 $0$ 时刻开始，每个时刻会有以下两件事发生：

1、对于每个房间 $k$ ，如果 $k$ 的儿子房间中有至少有一个居民知道了这一好消息，并且仍有其他 $k$ 的儿子房间中的居民尚末知情，则可以让恰好一个未知情的儿子房屋中的居民得知这一好消息。

2、小红可以任意选择一个未得知这一好消息的居民得知这一好消息。

小红想知道在最佳选择下，在第几个时刻后他能让所有 $n$ 个居民得知这一好消息？

输入描述

第一行 $1$ 个整数 $T$ ，表示数据组数。

对每组数据有 $2$ 行数据。

第一行一个整数 $n$ ，表示房间总数。

第二行 $n-1$ 个整数 $P_2,P_3,...,P_n$ 表示第 $i$ 个房间通过向上楼梯连接的房间号，保证形成合法的图论中的树结构。

$1≤T≤5,1≤n≤100000,1≤p_i≤n$

输出描述

对于每组数据，输出一行一个答案，表示最少需要的时刻数。

样例1

输入

1
6
1 1 2 2 2

输出

3

说明

样例如图所示

第 $1$ 时刻

第 $1$ 件事：因为还没有通知任何人，所以第 $1$ 件事无事发生。

第 $2$ 件事：小红选择了通知 $5$ 房间居民。

第 $2$ 时刻

第 $1$ 件事：对于房间 $2$ ，它有一个儿了房间 $5$ 已被通知，于是 $2$ 的儿子房间之间的相互通知，使得 $4$ 或 $6$ 中任意一个房间收到通知，这里假设是 $4$ 收到了通知。

第 $2$ 件事：小红选择了通知 $3$ 房间居民。

第 $3$ 时刻

第 $1$ 件事：对于房间 $2$ ，它儿子房间 $4$ 和 $5$ 都已收到通知，满足了至少有一个被通知，因此又会通知一个儿子房间，即剩下的那一个 $6$ 房间。

对于房间 $1$ ，它也有一个儿子房间 $3$ 收到通知了，于是会通知另一个儿子房间 $2$ 。

第 $2$ 件事：小红选择了通知 $1$ 房间居民。此刻结束后，所有的 $6$ 间房间的居民均已收到通知。