P5499 [LnOI2019] Abbi Does Not Want to Go on a Study Tour.

Problem provider: XuKaFy

**[Original Problem]** Given a tree with $n$ nodes. All leaf nodes are numbers, and all non-leaf nodes are symbols `+` or `*`. First, perform Heavy-Light Decomposition (HLD) on the tree. Note: if there is a tie in subtree size, choose the child with the smaller index as the heavy child. The value of a node is defined as follows: if the node is a leaf, its value is the number on the node; if the node is not a leaf, then its value is the result of applying `+` or `*` (depending on the node’s symbol) to the values of all nodes on the heavy chains of all its children that are **not on the same heavy chain as this node**. Another way to describe it is: let the set of children of node $i$ be $D_{i}$, the parent of node $i$ be $F_{i}$, and the set of nodes on the heavy chain containing node $i$ be $P_{i}$. Define: $$ Charge_{i}=\cup_{k\in D_{i},\ k\not\in P_{i}}P_{k} $$ Let $C_{i}$ be the symbol of this node. Then the value of this node is: $$ V_{i}= \begin{cases} \sum_{j\in Charge_{i}}V_{j} &C_{i}=`+'\\ \prod_{j\in Charge_{i}}V_{j} &C_{i}=`\times' \end{cases} $$ The data does not guarantee that every non-leaf node has at least one child outside its chain. If there is no valid child, ignore this node. You need to support three operations: 1. Change the value of a leaf node. 2. Change the symbol of a non-leaf node to `+` or `*`. 3. Query, for the heavy chain containing a given node, the sum and the product of the values of all nodes on that heavy chain. To prevent overflow, take all values modulo $99991$.

The first line contains two integers $n$ and $m$, meaning the number of students and the number of requests. Then input $1$ line with $n-1$ integers, meaning the parent of node $i+1$ is $a$. Then input one line with $n$ integers describing each node: if the node is a leaf, it is a number representing $V_{i}$; otherwise it is a number, where `0` means `+` and `1` means `*`. Then input $m$ lines. Each line contains an integer $c$ and an index $k$, meaning the request type is $c$ and the operated node index is $k$. If $c=1$, then input another integer $V_{i}$ as the new value.

For each operation of type $3$, output one line containing two integers $a, b$, meaning the sum **and** the product of the values of all nodes on the heavy chain containing this node.

For $30\%$ of the testdata, $1 \le n,m \le 1000$. For $100\%$ of the testdata, $1 \le n,m \le 10^{6}, 1 \le V_{i}