P10121 『STA - R4』Fuse.

APJ: "? Why is the fuse in my house gone again?"

You are given a rooted tree with $n$ nodes, where the root is node $1$. Define the distance between two node sets $S_1, S_2$ as the minimum distance between a node chosen from each set, i.e., $\displaystyle\operatorname{dist}(S_1,S_2)=\min_{\substack{u\in S_1\\v\in S_2}}\operatorname{dist}(u,v)$, where $\operatorname{dist}(u,v)$ is the distance between nodes $u$ and $v$. Define $\operatorname{path}(u,v)$ as the set of all nodes on the simple path from $u$ to $v$. Let $\mathcal L$ be the set of all leaves. For a fixed positive integer $u$, define the set of nodes $v$ that satisfy the following conditions to be the semi-neighborhood of $u$, denoted by $\mathring U(u)$: - $v$ is in the subtree of $u$. - $\operatorname{dist}(u,v)\le\operatorname{dist}(\operatorname{path}(1,v),\mathcal L)$. That is, the semi-neighborhood $\mathring U(u)$ contains all nodes $v$ in the subtree of $u$ such that the distance from $v$ to $u$ is no more than the distance from any node on the path from $v$ to the root to its nearest leaf node. Then define: $$f(x)=\sum_{u\in\mathring U(x)}\prod_{\substack{v\in\operatorname{subtree}(u)\\v\in\mathring U(x)}}F_{\deg v}$$ where $\operatorname{subtree}(u)$ is the set of all nodes in the subtree of $u$, $\deg u$ is the degree of $u$ (the number of nodes adjacent to $u$), and $F$ is the Fibonacci sequence: $$F_n=\begin{cases}1&n\le 2\\F_{n-1}+F_{n-2}&n\ge 3\end{cases}$$ In other words, $f(x)$ is the sum of contributions of nodes in the semi-neighborhood of $x$. The contribution of a node $u$ to $x$ is computed as follows: take every node $v$ in the subtree of $u$ that is also in the semi-neighborhood of $x$; if the degree of $v$ is $d$, then multiply the contribution of $u$ by $F_d$. The final result is the sum of contributions of all such $u$. You need to compute $f(1), f(2), \cdots, f(n)$. To reduce the output size, you only need to output the XOR of these values modulo $994007158$, i.e., $\bigoplus_{x=1}^n(f(x)\bmod 994007158)$.

The first line contains a positive integer $n$, the number of nodes. The second line contains $n - 1$ positive integers. The $i$-th integer represents the parent of node $i + 1$.

One line, the value of $\bigoplus_{x=1}^n(f(x)\bmod 994007158)$.

### Sample Explanation In the first sample, the values of $f$ at $1\dots 7$ are: $8,2,2,1,1,1,1$. In the second sample, the values of $f$ at $1\dots14$ are: $4,17,2,1,1,8,1,1,4,2,1,1,1,1$. ### Constraints **This problem uses bundled testdata.** - Subtask 1 (10 pts): $n\le 5000$. - Subtask 2 (20 pts): the number of leaves in the tree is at most $30$. - Subtask 3 (20 pts): there is no node in the tree that has exactly one child. - Subtask 4 (50 pts): no special restrictions. For all testdata, $2\le n,q\le 10^6$, and for each non-root node, its parent index is smaller than its own index. Translated by ChatGPT 5