P9775 [HUSTFC 2023] Generalized Segment Tree

For any sequence $a$ of length $n$, we can build a generalized segment tree based on $a$. A generalized segment tree is a weighted binary tree with $(2n-1)$ nodes. For each node with index $p$, it has two attributes $L_p$ and $R_p$, meaning that the interval it maintains is $[L_p, R_p]$, and its weight is $M_p =\prod_{i=L_p}^{R_p}a_i$. In addition, the generalized segment tree also satisfies the following properties: - All nodes with index $p\in [n,2n-1]$ are leaf nodes, and $L_p = R_p = p + 1 - n$. - All nodes with index $p\in [1,n-1]$ are non-leaf nodes. Each of them must have a left child $X_p$ and a right child $Y_p$, and $p < X_p < Y_p$. The interval maintained by node $p$ is the union of the intervals maintained by its two children, and it is guaranteed to be continuous. Formally, $R_{X_p}=L_{Y_p}-1$, and $L_p=L_{X_p}$, $R_p=R_{Y_p}$. For example, the following is a generalized segment tree built from $n=4$ and the sequence $a=\{1, 2, 3, 4\}$ (the integer pair $(p, M_p)$ inside each node denotes its index and weight, respectively). You can see that the shape of a generalized segment tree is not unique.  For this generalized segment tree: - $[L_7, R_7] = [4, 4]$, so $M_7 = a_4$ - $[L_6, R_6] = [3, 3]$, so $M_6 = a_3$ - $[L_5, R_5] = [2, 2]$, so $M_5 = a_2$ - $[L_4, R_4] = [1, 1]$, so $M_4 = a_1$ - $[L_3, R_3] = [L_4, R_5] = [1, 2]$, so $M_3 = a_1 \times a_2$ - $[L_2, R_2] = [L_3, R_6] = [1, 3]$, so $M_2 = a_1 \times a_2 \times a_3$ - $[L_1, R_1] = [L_2, R_7] = [1, 4]$, so $M_1 = a_1 \times a_2 \times a_3 \times a_4$ You are given two sequences $a$ and $b$ of length $n$, and the shape of a generalized segment tree $T$ with $(2n-1)$ nodes (that is, the indices of the left and right child for each node). Then you need to perform $n$ operations. In the $i$-th operation, change $a_i$ into $a_i\times b_i$. After each operation, you need to build a generalized segment tree with the same shape as $T$ based on the modified sequence $a$, and compute the sum of weights of all nodes, i.e. $\sum_{i=1}^{2n-1}M_i$. Since the result can be very large, you only need to output it modulo $998\,244\,353$.

The first line contains an integer $n\ (1\le n\le 5\cdot 10^5)$, representing the length of sequences $a$ and $b$. The second line contains $n$ integers, where the $i$-th integer is defined as $a_i\ (1 \le a_i < 998\,244\,353)$. The third line contains $n$ integers, where the $i$-th integer is defined as $b_i\ (1 \le b_i < 998\,244\,353)$. The next $n-1$ lines describe the tree. The $i$-th of these lines contains two integers $X_i, Y_i\ (i

Output one line with $n$ integers separated by spaces, where the $i$-th integer is the answer after the $i$-th modification modulo $998\,244\,353$.

In the sample, the shape of the generalized segment tree is the same as the example in the statement. After the first modification, $a_1$ becomes $a_1 \times b_1 = 1 \times 2 = 2$, so the new $a = \{2, 2, 3, 4\}$. We can compute: - $M_7 = a_4 = 4$ - $M_6 = a_3 = 3$ - $M_5 = a_2 = 2$ - $M_4 = a_1 = 2$ - $M_3 = a_1 \times a_2 = 2 \times 2 = 4$ - $M_2 = a_1 \times a_2 \times a_3 = 2 \times 2 \times 3 = 12$ - $M_1 = a_1 \times a_2 \times a_3 \times a_4 = 2 \times 2 \times 3 \times 4 = 48$ So the sum of weights is $M_1 + M_2 + \ldots + M_7 = 75$. After the second modification, $a_2$ becomes $a_2 \times b_2 = 2 \times 3 = 6$. The remaining operations are similar to the first one, so they are not repeated here. Translated by ChatGPT 5