{"problem":{"name":"『STA - R4』保险丝","description":{"content":"给一棵 $n$ 个点的有根树，根是 $1$ 号结点。 定义两个点集 $S_1,S_2$ 的距离为从两个集合分别选出一个点，能得到两点间距离的最小值，即 $\\displaystyle\\operatorname{dist}(S_1,S_2)=\\min_{\\substack{u\\in S_1\\\\v\\in S_2}}\\operatorname{dist}(u,v)$，其中 $\\operatorname{","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10121"},"statements":[{"statement_type":"Markdown","content":"给一棵 $n$ 个点的有根树，根是 $1$ 号结点。\n\n定义两个点集 $S_1,S_2$ 的距离为从两个集合分别选出一个点，能得到两点间距离的最小值，即 $\\displaystyle\\operatorname{dist}(S_1,S_2)=\\min_{\\substack{u\\in S_1\\\\v\\in S_2}}\\operatorname{dist}(u,v)$，其中 $\\operatorname{dist}(u,v)$ 是点 $u,v$ 间的距离。\n\n定义 $\\operatorname{path}(u,v)$ 是 $u$ 到 $v$ 的简单路径上的所有点组成的集合，$\\mathcal L$ 是所有叶子组成的集合。\n\n对于固定正整数 $u$，定义满足如下条件的结点 $v$ 构成 $u$ 的半邻域 $\\mathring U(u)$：\n- $v$ 在 $u$ 子树内；\n- $\\operatorname{dist}(u,v)\\le\\operatorname{dist}(\\operatorname{path}(1,v),\\mathcal L)$。\n\n即 $u$ 的半邻域 $\\mathring U(u)$ 包含 $u$ 的子树内所有满足到 $u$ 的距离不大于它到根的路径上任意一点离最近叶子节点的距离的点。\n\n进而定义：\n$$f(x)=\\sum_{u\\in\\mathring U(x)}\\prod_{\\substack{v\\in\\operatorname{subtree}(u)\\\\v\\in\\mathring U(x)}}F_{\\deg v}$$\n其中 $\\operatorname{subtree}(u)$ 是 $u$ 子树中所有点组成的集合，$\\deg u$ 是 $u$ 的度数（与 $u$ 有连边的点的数量），$F$ 是 Fibonacci 数列：\n$$F_n=\\begin{cases}1&n\\le 2\\\\F_{n-1}+F_{n-2}&n\\ge 3\\end{cases}$$\n\n即 $f(x)$ 对应 $x$ 的半邻域中点对 $x$ 的贡献之和。而一个点 $u$ 对 $x$ 的贡献的计算方式为：取出每个 $u$ 子树内处在 $x$ 半邻域中的点 $v$，若 $v$ 的度数为 $d$，则将 $u$ 的贡献乘上 $F_d$，所有 $u$ 的贡献之和为结果。\n\n你需要求出 $f(1),f(2),\\cdots,f(n)$ 的值，为减少输出量，你只需要输出它们模 $994007158$ 后的异或和，即 $\\bigoplus_{x=1}^n(f(x)\\bmod 994007158)$ 即可。\n\n## Input\n\n第一行一个正整数 $n$ 表示点数。\n\n第二行 $n - 1$ 个正整数，第 $i$ 个正整数代表了结点 $i + 1$ 的父亲结点。\n\n## Output\n\n一行，表示 $\\bigoplus_{x=1}^n(f(x)\\bmod 994007158)$ 的值。\n\n[samples]\n\n## Background\n\nAPJ：「？我家保险丝怎么又没了」\n\n## Note\n\n### 样例解释\n第一组数据中 $f$ 在 $1\\dots 7$ 处的取值：$8,2,2,1,1,1,1$。\n\n第二组数据中 $f$ 在 $1\\dots14$ 处的取值：$4,17,2,1,1,8,1,1,4,2,1,1,1,1$。\n### 数据范围\n\n**本题采用捆绑测试。**\n- Subtask 1 (10pts)：$n\\le 5000$。\n- Subtask 2 (20pts)：树的叶子个数不大于 $30$。\n- Subtask 3 (20pts)：树中没有恰有一个儿子的结点。\n- Subtask 4 (50pts)：无特殊限制。\n\n对于全部数据，$2\\le n,q\\le 10^6$，每个非根结点父亲的编号小于它的编号。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10121","tags":["暴力数据结构","线段树","O2优化","树论","虚树","其它技巧"],"sample_group":[["7\n1 1 2 2 3 3\n","8"],["14\n1 2 3 3 2 6 6 6 9 9 10 11 12","25"]],"created_at":"2026-03-03 11:09:25"}}