P16463 [UOI 2026] Color the Tree

给定一棵有 $n$ 个顶点的有根树，树根为顶点 $1$。 对于每个顶点 $v$，你需要选择一个数字 $c_v$，其值为 $1$ 或 $2$。这样的数字选择方案称为该树的一种**涂色**。 对于每个顶点 $v$，考虑树中从顶点 $1$ 到顶点 $v$ 的唯一路径。令 $s_v$ 为该路径上所有顶点对应的数字 $c_u$ 之和，包括顶点 $1$ 和 $v$ 自身。 如果所有 $s_1, s_2, \ldots, s_n$ 两两不同（即没有两个值相等），则称该涂色是**正确的**。 请你计算这棵树正确的涂色方案数量。 由于答案可能很大，请将其对 $10^9 + 7$ 取模后输出。

第一行包含一个整数 $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$ 的父顶点。 这意味着对于每个 $i$ 从 $2$ 到 $n$，顶点 $p_i$ 与顶点 $i$ 之间有一条边，且顶点 $p_i$ 离根更近。 保证所有测试数据的 $n$ 之和不超过 $2 \cdot 10^5$。

对于每组测试数据，输出一个整数 —— 该树正确的涂色方案数量对 $10^9 + 7$ 取模的结果。

在第一个样例中，顶点 $2$ 和 $3$ 是根的子顶点。 以下涂色方案是正确的：$\{1, 1, 2\}$，$\{1, 2, 1\}$，$\{2, 1, 2\}$，$\{2, 2, 1\}$。 因此答案为 $4$。 ### 计分 一个顶点 $v$ 的子顶点是指满足 $p_u = v$ 的顶点 $u$。 叶子是指没有子顶点的顶点。 树中两个顶点之间的距离是指它们之间唯一路径上的边数。 - （$11$ 分）：$n \le 10$ 且 $t = 1$。 - （$6$ 分）：每个顶点至多有一个子顶点，且 $t = 1$。 - （$7$ 分）：每个顶点到根的距离不超过 $2$ 条边，且 $t = 1$。 - （$8$ 分）：树中至多有一个顶点恰好拥有两个子顶点；其他所有顶点至多有一个子顶点，且 $t = 1$。 - （$12$ 分）：只有根可以拥有多于一个子顶点，且 $t = 1$。 - （$13$ 分）：叶子的数量不超过 $3$，且 $t = 1$。 - （$11$ 分）：恰好拥有两个子顶点的顶点数量不超过 $20$，且 $t = 1$。 - （$15$ 分）：$n \le 1000$。 - （$17$ 分）：无额外限制。 翻译由 DeepSeek V4 Pro 完成