CF2238C Village Guilds

嗯嗯嗯。 —— Minecraft 在他漫长的冒险途中，Steve 偶然发现了一个村民村庄。村庄中的房屋通过双向小路相连。该村共有 $n$ 座房屋，编号从 $1$ 到 $n$。这些房屋和小路构成了一棵有根树$^{\text{∗}}$，根节点为 $1$ 号房屋（即市政厅）。 现在，考虑任意一个房屋 $v$ 及其子树$^{\text{‡}}$。对于每个这样的房屋 $v$ 以及每个非负整数 $h$，考虑在 $v$ 的子树内、与 $v$ 的距离恰好为 $h$ 的所有房屋所组成的集合。这样一个集合被称为一个公会（guild）。例如，当 $h=0$ 时，公会只包含房屋 $v$ 本身。 在下图中，给出了以 $v=4$ 为根的若干公会示意图。$h=0$ 时的公会用红色标记，$h=1$ 时用浅蓝色标记，$h=2$ 时用绿色标记。  如果存在某个房屋属于一个公会而不属于另一个公会，那么这两个公会被认为是不同的。Steve 想知道，该树中总共有多少种不同的非空公会。请帮他计算出来。 $^{\text{∗}}$ 有根树是指一棵特殊指定了根节点的树。 $^{\text{†}}$ 树是指一种无环连通图。 $^{\text{‡}}$ 顶点 $v$ 的子树指的是包含 $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 < i$），其中 $p_i$ 表示在树中第 $i$ 号房屋的父节点编号。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示该村庄中互不相同的公会（非空集合）的数量。

在第一个测试用例中，共有 $5$ 个公会，每个都只包含一个房屋。 在第二个测试用例中，除了每个房屋各自组成的公会外，还有一个公会由房屋 $2$ 和 $3$ 组成。它可以通过考虑以 $v=1$ 为根、$h=1$ 的情况得到。 在第三个测试用例中，除了每个房屋的单独公会，还有另外两个公会：以 $v=1$ 为根且 $h=1$ 时，公会包含房屋 $2$ 和 $4$；以 $v=5$ 为根且 $h=1$ 时，公会包含房屋 $6$ 和 $7$。  由 ChatGPT 5 翻译