{"problem":{"name":"『XYGOI round1』一棵树","description":{"content":"于是 MX 有一棵 $n$ 个节点的树，每个点上有一个数字 $a_i$。 定义一条路径 $(x,y)$ 的权值 $w(x,y)$ 为，从 $x$ 走到 $y$ 的最短路径上，所有节点上的数字顺次写下后得到的数。如，顺次经过写有数字 $3,21,0,5$ 的四个节点，那么这个路径的权值为 $32105$。 MX 想知道这棵树所有路径的权值之和，即 $\\sum\\limits_{x=1}^n\\sum","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9437"},"statements":[{"statement_type":"Markdown","content":"于是 MX 有一棵 $n$ 个节点的树，每个点上有一个数字 $a_i$。\n\n定义一条路径 $(x,y)$ 的权值 $w(x,y)$ 为，从 $x$ 走到 $y$ 的最短路径上，所有节点上的数字顺次写下后得到的数。如，顺次经过写有数字 $3,21,0,5$ 的四个节点，那么这个路径的权值为 $32105$。\n\nMX 想知道这棵树所有路径的权值之和，即 $\\sum\\limits_{x=1}^n\\sum\\limits_{y=1}^nw(x,y)$ 为多少。\n\n答案可能很大，对 $998244353$ 取模。\n\n## Input\n\n第一行一个正整数 $n$。\n\n第二行 $n$ 个非负整数 $a_i$。\n\n第三行 $n-1$ 个正整数，第 $i$ 个数 $p_i$ 表示节点 $p_i$ 与节点 $i+1$ 之间有边。保证 $1\\le p_i\\le i$。\n\n## Output\n\n一行一个整数，表示答案。答案对 $998244353$ 取模。\n\n[samples]\n\n## Background\n\njava 今天带了一棵树到出题组，然后被不讲理的 MX 占为己有了。\n\n## Note\n\n### 样例解释\n\n样例一解释：$1+12+123+2+21+23+3+32+321=538$。\n\n样例二解释：$5+521+5210+21+215+210+0+021+0215=6418$。\n\n### 数据范围  \n**本题采用捆绑测试。**  \n\n记 $V=\\max\\{a_i\\}+1$。\n\n|Subtask|分值|$n\\le$|$V\\le $|特殊性质|\n|:-:|:-:|:-:|:-:|:-:|\n|0|5|$1000$|$10$||\n|1|15|$8000$|$10^9$||\n|2|15|$10^6$|$10^9$|$p_i=i$|\n|3|15|$10^6$|$10^9$|$p_i=1$|\n|4|50|$10^6$|$10^9$||\n\n对于 $100\\%$ 的数据，$1\\le n\\le 10^6$，$0\\le a_i<10^9$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9437","tags":["动态规划 DP","O2优化","树形 DP","洛谷月赛"],"sample_group":[["3\n1 2 3\n1 2","538"],["3\n5 21 0\n1 2","6418"],["4\n1 2 3 4\n1 2 2\n","1900"],["6\n10 23 16 3 125 1\n1 1 1 1 1\n","7680868"]],"created_at":"2026-03-03 11:09:25"}}