P12355 「HCOI-R2」Tour

Little A is a famous singer from the country of HCOI, and she plans to embark on a tour.

The country of HCOI consists of $n$ cities, which is abstracted as a rooted tree with $n$ nodes, where the capital is the root $r$. Little A plans to start from $r$ and traverse all cities for a performance. Specifically, let $x$ be Little A’s current position, and define a sequence $s$ as follows: - Initially, $x = r$ and $s = [r]$. - If $x$ has unvisited children, arbitrarily choose one child $y$, append $y$ to the end of $s$, and move to $y$. - If no such $y$ exists: If $x = r$, the performance ends. Otherwise, move to $x$'s parent. The final sequence $s$ is called a traversal method of $T$. Different choices of children yield multiple traversal methods. Note that traversal methods are essentially DFS orders of $T$. Little A's assistant provides a fee table $\{w_{n-1}\}$. The revenue $w(T, s)$ of the tour is defined as: - For $i \in [2, n]$, Little A traverses the simple path $s_{i-1} \to s_i$ on $T$ (excluding $s_{i-1}$, including $s_i$). - Each time a node is visited, if it is the $i$-th time of arrival, Little A receives $w_i$ gold coins as payment. - $w(T, s)$ is the total number of gold coins Little A collects. The assistant also provides the traversal method $\{s_n\}$ for this performance. Little A tree $T$ is defined as valid if and only if $\{s_n\}$ is one of its traversal methods. You need to compute the sum of $w(T, s)$ over all distinct valid trees $T$, modulo $998244353$. Two trees $T$ and $T'$ are considered distinct if they have different roots or there exists an edge present in one tree but not the other.

**Each single test case has multiple sets of test data.** The first line contains a positive integer $T$ representing the number of test cases. For each test case: The first line contains a positive integer $n$, indicating the number of cities in HCOI. The second line contains $n$ positive integers $s_1, s_2, \cdots, s_n$, representing the traversal method of A’s performance. The third line contains $n-1$ non-negative integers $w_1, w_2, \cdots, w_{n-1}$, representing the fee table for the performance.

For each test case, output a single line of integer representing the sum of all valid $T$'s $w(T)$ modulo $998244353$.

### Constraints **This problem uses subtasks.** | Subtask | $\boldsymbol{n\le}$ | $\boldsymbol{\sum n\le}$ | Special Property | Score | | :----------: | :----------: | :----------: | :----------: | :----------: | | $0$ | $4$ | $10^6$ | A | $5$ | | $1$ | $8$ | $40$ | A | $15$ | | $2$ | $12$ | $60$ | None | $10$ | | $3$ | $50$ | $200$ | None | $10$ | | $4$ | $100$ | $500$ | None | $10$ | | $5$ | $10^3$ | $5\times 10^3$ | B | $10$ | | $6$ | $10^3$ | $5\times 10^3$ | None | $5$ | | $7$ | $10^5$ | $2\times 10^5$ | B | $5$ | | $8$ | $10^5$ | $2\times 10^5$ | None | $15$ | | $9$ | $5\times10^5$ | $10^6$ | None | $15$ | - **Special Property A**: For all $i \in [1, n]$, $s_i = i$. - **Special Property B**: $w_1 = 1$, and for all $i \in [2, n-1]$, $w_i = 0$. For all test cases, it is guaranteed that $1 \le T \le 10^5$, $2 \le n \le 5 \times 10^5$, $\sum n \le 10^6$, $0 \le w_i < 998244353$, $\{s_n\}$ is a permutation of $1,2,\cdots,n$.