Expected Minimum in Random DFS on a Tree

Kyujo, a girl who loves algorithms – especially depth‐first search (DFS) – has obtained a rooted tree. The tree’s root is denoted by \(\mathtt{root}\) and every node \(x\) has an associated weight \(a_x\).

For any two nodes \(x\) and \(y\) such that \(y\) is in the subtree of \(x\) (we call the pair \((x,y)\) valid), consider the following randomized DFS process to search for \(y\) starting at \(x\):

1. Initialize an empty recursion stack.
2. Push \(x\) onto the stack.
3. Repeat: Pop the top \(u\) of the stack. If \(u=y\), stop. Otherwise, if \(u\) has unvisited direct children, choose one uniformly at random and push it onto the stack. If no unvisited child exists, backtrack (i.e. pop back to the previous recursion level) and continue.
4. The process terminates when the search starting at \(x\) ends (which happens after visiting \(y\)).

During this DFS the set of visited nodes consists of all nodes pushed onto the recursion stack (including \(x\) and \(y\)). Define \(f(x,y)\) as the expected value of the minimum weight among all visited nodes, i.e.,

[ f(x,y)=\mathbb{E}\Bigl(\min{a_z: z \text{ is visited in the DFS from } x \text{ to } y}\Bigr). ]

Your task is to compute the sum of \(f(x,y)\) over all valid pairs \((x,y)\) and output the answer modulo \(998244353\). More precisely, if the answer in lowest terms is \(\frac{a}{b}\), you should output \(a \times b^{-1} \bmod 998244353\).

Note on the DFS process:

When exploring from a node \(x\), suppose the unique path from \(x\) to \(y\) is \(x=v_0,v_1,\dots,v_k=y\). At each node \(v_i\) (for \(0 \le i < k\)), let its children be \(\{v_{i+1}\}\) (the designated child on the path) plus some extra children. In the DFS the order in which the children are processed is uniformly random. Therefore, if at a node with extra children, some of these extra subtrees are explored (that is, they appear before the designated child in the random order), then all nodes in that subtree are visited. In particular, for each extra child \(u\) of \(v_i\), the entire subtree rooted at \(u\) is visited with probability \(\frac{1}{2}\) (since in a random permutation any particular child appears before the designated one with probability \(\frac{1}{2}\)).

Hence, for a DP formulation one may observe that if we denote by \(m_{\mathtt{full}}(u)=\min\{a_z: z \in \text{subtree of } u\}\) then the visited set when going from \(x\) to \(y\) always contains the path \(x=v_0, v_1,\dots,v_k=y\) (with minimum \(D=\min_{0\le i\le k}a_{v_i}\)), plus, for each node \(v_i\ (0\le i<k)\) an independent extra branch (each with probability \(\frac{1}{2}\)) whose value candidate is \(m_{\mathtt{full}}(u)\). The overall expected minimum is then computed by taking the minimum of \(D\) and the candidates from those branches that are visited.

This problem requires summing \(f(x,y)\) over all valid pairs \((x,y)\). It is guaranteed that the input size is small enough that an \(O(n^2)\) solution will pass.

inputFormat

The first line contains a single integer \(n\) \((1 \le n \le \text{small})\) denoting the number of nodes in the tree. The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) where \(a_i\) is the weight of node \(i\). Nodes are numbered from 1 to \(n\); node 1 is the root. Each of the next \(n-1\) lines contains one integer. For \(i=2,3,\dots,n\), the \(i\)th line gives the parent of node \(i\).

outputFormat

Output a single integer, the sum of \(f(x,y)\) for all valid pairs \((x,y)\) modulo \(998244353\).

sample

3
3 2 5
1
1

499122186