P9776 [HUSTFC 2023] Narrow Segment Tree

You plan to build a binary tree with $(2n - 1)$ nodes, among which there are $n$ leaf nodes. Specifically, the pseudocode for building this tree is shown in the figure.  It is not hard to see that node $1$ is the root, and the indices of all nodes are the same as their DFS order. Also, you consider leaf nodes very important, so you rename these $n$ leaf nodes, in increasing order of node indices, as leaf $1$, leaf $2$, $\dots$, leaf $n$. Leaf nodes are governed by the nodes above them. More precisely, if leaf $i$ is in the subtree of node $j$, then node $j$ governs leaf $i$, and we write $g(j,i)=1$; otherwise, if node $j$ does not govern leaf $i$, then $g(j,i)=0$. Note that a leaf node also governs itself. Meanwhile, you think a good binary tree should have node weights. For node $i$, define its node weight as $v_i$. Initially, the node weights of all nodes are $0$. In a dream, you are modifying this binary tree. You will perform $q$ operations on this binary tree in order. The format and description of each operation are as follows: - $1\ s\ t\ v$: For all integers $i\ (i\in [s,t])$, add $v$ to the node weight of node $i$. - $2\ s\ t\ v$: Let $\mathcal{S}={\textstyle \bigcup_{i\in [s,t]}}S_i$, where $S_i$ denotes the set of leaf nodes governed by node $i$. Then, for all leaf nodes in $\mathcal{S}$, add $v$ to their node weights. Note that $\mathcal{S}$ is a set without duplicates, i.e., in this operation, each leaf node is modified at most once. - $3\ l\ r$: Compute $\sum^{r}_{i=l}f(i)\bmod 998\,244\,353$, where $f(i)$ is the sum of the node weights of all nodes that govern leaf $i$, i.e., $f(i)=\sum_{g(j,i)=1}{v_j}$. You want to add more operations, but the 8 a.m. bell wakes you up. Still, you decide to implement this whimsical idea.

The first line contains an integer $n\ (3\le n\le 10^5)$, representing the number of leaf nodes in the binary tree. The second line contains $(2n-2)$ integers, where the $i$-th integer represents the parent index of node $i+1$. It is guaranteed that the given tree shape matches the node indices and the description in the statement. The third line contains an integer $q\ (3\le q\le 10^5)$, representing the number of operations. In the next $q$ lines, the first integer $opt\ (opt\in [1, 3])$ indicates the operation type. If $opt=1$ or $opt=2$, it is followed by three integers $s,t,v\ (1\le s\le t\le 2n-1,\ 0\le v

For each operation with $opt=3$, output one line with one integer, representing the result of this query.

Translated by ChatGPT 5