CF2238C.Village Guilds

Hmmmrmm.

— Minecraft

During his long adventure, Steve stumbled upon a village of villagers. The houses in the village are connected by bidirectional paths. In total, there are $n$ houses in the village, numbered from $1$ to $n$. The graph of houses and paths represents a rooted$^{\text{∗}}$ tree$^{\text{†}}$, rooted at vertex $1$, where the town hall is located.

Consider an arbitrary house $v$ and its subtree$^{\text{‡}}$. For each such house $v$ and each non-negative integer $h$, consider the set of houses that are in the subtree of $v$ at a distance exactly $h$ from $v$. Such a set will be called a guild. For example, for $h=0$, the guild will consist only of the vertex $v$.

In the example below, the guilds for the vertex $v=4$ are shown. The guild for $h=0$ is marked in red, for $h=1$ in light blue, and for $h=2$ in green.

Two guilds are considered different if there exists a house that is in one guild and not in the other. Steve wants to know how many different non-empty guilds there are in the tree. Help him with this.

$^{\text{∗}}$A rooted tree is a tree where one vertex is special and called the root.

$^{\text{†}}$A tree is a connected graph without cycles.

$^{\text{‡}}$A subtree of vertex $v$ is the subgraph of $v$, all its descendants, and all the edges between them.

Hmmmrmm。

——《我的世界》

在漫长的冒险途中，史蒂夫偶然发现了一个村民村庄。村庄中的房屋由双向路径连接。村庄中共有 $n$ 座房屋，编号从 $1$ 到 $n$。这些房屋与路径构成的图是一棵有根树$^{\text{∗}}$，根节点为顶点 $1$（即市政厅所在地）。

考虑任意一座房屋 $v$ 及其子树$^{\text{‡}}$。对每个这样的房屋 $v$ 和每个非负整数 $h$，定义集合：该集合包含所有位于 $v$ 的子树中、且到 $v$ 的距离恰好为 $h$ 的房屋。该集合称为一个公会（guild）。例如，当 $h = 0$ 时，该公会仅包含顶点 $v$ 自身。

下图展示了顶点 $v = 4$ 对应的各个公会。其中 $h = 0$ 的公会以红色标出，$h = 1$ 的公会以浅蓝色标出，$h = 2$ 的公会以绿色标出。

若存在某座房屋属于其中一个公会但不属于另一个，则称这两个公会不同。史蒂夫想知道：这棵树中一共有多少个互不相同且非空的公会？请帮他解决这个问题。

$^{\text{∗}}$ 有根树是指一棵树中指定一个特殊顶点作为根节点。

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

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

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of houses in the village.

The second line contains $n-1$ integers $p_2, p_3, \ldots, p_n$ ($1 \le p_i \lt i$), where $p_i$ is the parent of the $i$-th house in the tree.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case, output a single integer — the number of different guilds in the village.

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

In the first testcase, there are $5$ guilds, each consisting of a single house.

In the second testcase, in addition to the guilds consisting of a single house, there is also a guild consisting of vertices $2$ and $3$. It can be obtained by considering houses at distance $h=1$ in the subtree of vertex $v=1$.

In the third testcase, in addition to the guilds consisting of a single house, there are $2$ more guilds: for $v=1$ and $h=1$, the guild consists of vertices $2$ and $4$; for $v=5$, $h=1$, the guild consists of vertices $6$ and $7$.

在第一个测试用例中，共有 $5$ 个公会，每个公会仅包含一座房屋。

在第二个测试用例中，除包含单座房屋的公会外，还存在一个由顶点 $2$ 和 $3$ 组成的公会。该公会可通过考虑顶点 $v=1$ 的子树中距离为 $h=1$ 的房屋得到。

在第三个测试用例中，除包含单座房屋的公会外，还额外存在 $2$ 个公会：当 $v=1$、$h=1$ 时，公会由顶点 $2$ 和 $4$ 组成；当 $v=5$、$h=1$ 时，公会由顶点 $6$ 和 $7$ 组成。