410474: GYM104024 F Subsequence

Aqua and Hiyori love subsequences.

Today, Aqua finds a cute tree. A tree is an undirected acyclic graph and this cute tree's root is vertex $$$1$$$. Now, Aqua colors the vertices in the tree and the color of vectex $$$i$$$ is $$$a_i$$$. In order to examine Aqua, Hiyori sets a problem.

A subsequence $$$A$$$ is defined as some sequences like $$$\lbrace u_1,u_2,\cdots,u_k\rbrace(k\geq 1)$$$, and it satisfies that $$$u_i$$$ is $$$u_{i+1}$$$'s ancestor for every $$$i=1,2,\cdots,k-1$$$. Meanwhile, the color of the subsequence $$$A$$$ is $$$\lbrace a_{u_1},a_{u_2},\cdots,a_{u_k}\rbrace$$$.

Define $$$T$$$ as the multiset of all subsequences' color in the tree, and $$$P(T)$$$ as the set of all subsequences' color in the tree. Let $$$v_x$$$ be the number of the subsequence $$$x$$$'s color appearing in $$$T$$$.

Now, Aqua should get $$$\sum_{x\in P(T)} v_x^2$$$. But she is stupid, could you help her?

There are three lines in the input.

The first line contains a integer $$$n\ (1\leq n\leq 5\cdot 10^3)$$$, represents the size of tree.

The second line contains $$$n$$$ integers $$$a_1,a_2,\cdots,a_n\ (0\leq a_i\leq 10^9)$$$, represents the color of vertex $$$i$$$.

The third line contains $$$n-1$$$ integer $$$p_2,p_3,\cdots,p_n\ (1\leq p_i\leq i-1)$$$, represents the father of vertex $$$i$$$.

Print one line. The only line should contain the answer modulo $$$998244353$$$.

3
1 2 3
1 1

5

3
1 1 1
1 1

13

In the second sample, $$$T=\lbrace \lbrace 1\rbrace,\lbrace 1\rbrace,\lbrace 1\rbrace,\lbrace 1,1\rbrace,\lbrace 1,1\rbrace\rbrace, P(T)=\lbrace\lbrace 1\rbrace,\lbrace 1,1\rbrace\rbrace$$$, so the answer is $$$3^2+2^2=13$$$.