← 返回题目列表

Codeforces · 1994/E

E. 木制游戏

中文机器翻译题面 查看原题

你会得到一片由$$$k$$$根树$$$^{\text{*}}$$$组成的森林。伐木工人 Timofey 希望通过执行以下操作来砍伐整个森林:

- 选择其中一棵树的任意顶点的子树$$$^{\text{†}}$$$,并将其从树中删除。

Timofey 喜欢按位运算,因此他希望删除的子树大小的按位或最大。帮助他并找到他可以获得的最大结果。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。然后是测试用例的描述。

每个测试用例的第一行包含一个整数 $$$k$$$ ($$$1 \leq k \leq 10^6$$$) — 森林中树木的数量。

接下来是每个 $$$k$$$ 树的描述:

第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^6$$$) — 树的大小。树的顶点用从 $$$1$$$ 到 $$$n$$$ 的整数进行编号。树的根是顶点号$$$1$$$。

第二行包含 $$$n - 1$$$ 整数 $$$p_2, p_3, \ldots p_n$$$ ($$$1 \leq p_i < i$$$),其中 $$$p_i$$$ — 顶点 $$$i$$$ 的父顶点。

保证所有输入数据集的$$$k$$$和$$$n$$$之和不超过$$$10^6$$$。

输出

对于每个测试用例,输出一个整数——可以获得的最大结果。

示例

输入 #1

3
1
1
2
4
1 2 2
6
1 1 3 1 3
1
10
1 2 2 1 1 5 7 6 4

输出 #1

1
7
10

注意

在第二个测试用例中,树看起来像这样:

第一个操作删除整个第二棵树。

第二个操作从第一棵树中删除顶点 $$$4$$$。

第三个操作删除第一棵树。结果是 $$$6|1|3 = 7$$$ ($$$|$$$ 表示按位或)。

在第三个测试用例中,需要删除整棵树。