Description

[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$.

Input Format

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.

Output Format

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.

8 5
1 2 3 3 2 2 7
1 0 1 3 4 5 0 6
3 1
2 2
3 1
1 4 1
3 1

18 132
37 360
35 120

Hint

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}<99991$.

The testdata guarantees that at any time there is no node on the tree whose value is $0$.

Translated by ChatGPT 5