← 返回题目列表

Codeforces · 2238/C

C. 村庄行会

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

嗯嗯嗯。
— 我的世界

在他的漫长冒险中,史蒂夫偶然发现了一个村民村庄。村里的房子有双向小路相连。村里总共有$$$n$$$间房屋,编号从$$$1$$$到$$$n$$$。房屋和路径图表示一棵有根$$$^{\text{*}}$$$ 树$$$^{\text{†}}$$$,根位于市政厅所在的顶点$$$1$$$。

考虑任意房屋 $$$v$$$ 及其子树$$$^{\text{‡}}$$$。对于每个这样的房子 $$$v$$$ 和每个非负整数 $$$h$$$,考虑 $$$v$$$ 子树中与 $$$v$$$ 距离恰好 $$$h$$$ 的房子集合。这样的集合将被称为 公会。例如,对于 $$$h=0$$$,公会将仅由顶点 $$$v$$$ 组成。

在下面的示例中,显示了顶点 $$$v=4$$$ 的行会。 $$$h=0$$$ 的公会标记为红色,$$$h=1$$$ 的公会标记为浅蓝色,$$$h=2$$$ 的公会标记为绿色。

如果存在一个属于一个公会而不属于另一个公会的房屋,则两个公会被视为不同。史蒂夫想知道树中有多少个不同的非空公会。帮助他解决这个问题。

$$$^{\text{*}}$$$有根树是一棵树,其中一个顶点是特殊的,称为根。

$$$^{\text{†}}$$$树是没有环的连通图。

$$$^{\text{‡}}$$$顶点 $$$v$$$ 的子树是 $$$v$$$ 的子图、其所有后代以及它们之间的所有边。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 村庄中的房屋数量。

第二行包含 $$$n-1$$$ 整数 $$$p_2, p_3, \ldots, p_n$$$ ($$$1 \le p_i \lt i$$$),其中 $$$p_i$$$ 是树中第 $$$i$$$ 房子的父代。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数——村庄中不同行会的数量。

示例

输入
复制

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

输出
复制

5
4
9
15
22

注意

在第一个测试用例中,有 $$$5$$$ 公会,每个公会由一个房屋组成。

在第二个测试用例中,除了由单个房屋组成的行会之外,还有一个由顶点$$$2$$$和$$$3$$$组成的行会。它可以通过考虑顶点 $$$v=1$$$ 的子树中距离 $$$h=1$$$ 处的房屋来获得。

在第三个测试用例中,除了由单个房屋组成的行会之外,还有$$$2$$$行会:对于$$$v=1$$$和$$$h=1$$$,行会由顶点$$$2$$$和$$$4$$$组成;对于 $$$v=5$$$、$$$h=1$$$,公会由顶点 $$$6$$$ 和 $$$7$$$ 组成。