P16463 [UOI 2026] Color the Tree

You are given a rooted tree with $n$ vertices. The root of the tree is vertex $1$. For each vertex $v$, you need to choose a number $c_v$ equal to either $1$ or $2$. Such a choice of numbers will be called a coloring of the tree. For each vertex $v$, consider the unique path in the tree from vertex $1$ to vertex $v$. Let $s_v$ be the sum of all numbers $c_u$ on this path, including vertices $1$ and $v$. A coloring is called correct if all numbers $s_1, s_2, \ldots, s_n$ are pairwise distinct, that is, no two of them are equal. Count the number of correct colorings of the tree. Since the answer may be very large, output it modulo $10^9 + 7$.

The first line contains one integer $t$ $(1 \le t \le 10^4)$ --- the number of test cases. Each test case consists of two lines. The first line of each test case contains one integer $n$ $(2 \le n \le 2 \cdot 10^5)$ --- the number of vertices in the tree. The second line contains $n-1$ integers $p_2, p_3, \ldots, p_n$ $(1 \le p_i < i)$, where $p_i$ is the parent of vertex $i$. This means that for each $i$ from $2$ to $n$, vertices $p_i$ and $i$ are connected by an edge, and vertex $p_i$ is closer to the root. It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

For each test case, output one integer --- the number of correct colorings of the tree modulo $10^9 + 7$.

In the first example, vertices $2$ and $3$ are children of the root. The following correct colorings are possible: $\{1, 1, 2\}$, $\{1, 2, 1\}$, $\{2, 1, 2\}$, $\{2, 2, 1\}$. So, the answer is $4$. ### Scoring A child of vertex $v$ is a vertex $u$ such that $p_u = v$. A leaf is a vertex that has no children. The distance between two vertices of a tree is the number of edges on the unique path between them. - ($11$ points): $n \le 10$ and $t = 1$. - ($6$ points): each vertex has at most one child and $t = 1$. - ($7$ points): each vertex is at distance at most $2$ edges from the root and $t = 1$. - ($8$ points): the tree has at most one vertex with exactly two children; all other vertices have at most one child, and $t = 1$. - ($12$ points): only the root may have more than one child and $t = 1$. - ($13$ points): the number of leaves does not exceed $3$ and $t = 1$. - ($11$ points): the number of vertices with exactly two children does not exceed $20$ and $t = 1$. - ($15$ points): $n \le 1000$. - ($17$ points): No additional constraints.