『XYGOI round1』一棵树
题目背景
java 今天带了一棵树到出题组,然后被不讲理的 MX 占为己有了。
题目描述
于是 MX 有一棵 $n$ 个节点的树,每个点上有一个数字 $a_i$。
定义一条路径 $(x,y)$ 的权值 $w(x,y)$ 为,从 $x$ 走到 $y$ 的最短路径上,所有节点上的数字顺次写下后得到的数。如,顺次经过写有数字 $3,21,0,5$ 的四个节点,那么这个路径的权值为 $32105$。
MX 想知道这棵树所有路径的权值之和,即 $\sum\limits_{x=1}^n\sum\limits_{y=1}^nw(x,y)$ 为多少。
答案可能很大,对 $998244353$ 取模。
输入输出格式
输入格式
第一行一个正整数 $n$。
第二行 $n$ 个非负整数 $a_i$。
第三行 $n-1$ 个正整数,第 $i$ 个数 $p_i$ 表示节点 $p_i$ 与节点 $i+1$ 之间有边。保证 $1\le p_i\le i$。
输出格式
一行一个整数,表示答案。答案对 $998244353$ 取模。
输入输出样例
输入样例 #1
3
1 2 3
1 2
输出样例 #1
538
输入样例 #2
3
5 21 0
1 2
输出样例 #2
6418
输入样例 #3
4
1 2 3 4
1 2 2
输出样例 #3
1900
输入样例 #4
6
10 23 16 3 125 1
1 1 1 1 1
输出样例 #4
7680868
说明
### 样例解释
样例一解释:$1+12+123+2+21+23+3+32+321=538$。
样例二解释:$5+521+5210+21+215+210+0+021+0215=6418$。
### 数据范围
**本题采用捆绑测试。**
记 $V=\max\{a_i\}+1$。
|Subtask|分值|$n\le$|$V\le $|特殊性质|
|:-:|:-:|:-:|:-:|:-:|
|0|5|$1000$|$10$||
|1|15|$8000$|$10^9$||
|2|15|$10^6$|$10^9$|$p_i=i$|
|3|15|$10^6$|$10^9$|$p_i=1$|
|4|50|$10^6$|$10^9$||
对于 $100\%$ 的数据,$1\le n\le 10^6$,$0\le a_i<10^9$。