[LnOI2019]Abbi并不想研学

题目背景

题目提供者:XuKaFy

题目描述

【原版题目】 给定一颗$n$个节点的树,树的叶节点全部是数字,非叶节点全部是符号`+`或者`*`。 请先对该树进行树链剖分。注意:若出现子树大小相同的情况,请选择编号较小的子节点作为重儿子。 一个节点的权值这样计算:若该节点为叶节点,数值即为节点数值;若该节点非叶节点,则该点的权值为【【【该点的【所有不在该点所在重链上】的子节点】所在重链的所有节点权值】相`+`或者相`*`的结果(操作取决于该节点的符号)】。 另一种表示方式是:设某一节点$i$的儿子集合为$D_{i}$,节点$i$的父亲为$F_{i}$,节点$i$的所在重链节点集合为$P_{i}$。 我们设: $$Charge_{i}=\cup_{k\in D_{i},\ k\not\in P_{i}}P_{k}$$ 令$C_{i}$为这个节点的符号,这个节点的权值就是: $$ 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} $$ 数据不保证每一个非叶节点都有至少一个非链上儿子,若没有合法的儿子则忽略该节点。 你需要支持这三种操作: - $1$.改变某一叶节点的数值; - $2$.改变某一非叶节点的符号为`+`或者`*`; - $3$.查询某一节点所在重链所有节点权值相`+`与相`*`的值。 为防止溢出,请将所有权值$mod\ 99991$。

输入输出格式

输入格式


第一行输入两个数$n$与$m$表示学生数量与要求数量。 接下来输入$1$行,$n-1$个数,表示第$i+1$个节点的父亲为$a$。 接下来一行$n$个数,分别为每个节点的信息:若该节点为叶节点,则是一个数字表示$V_{i}$,否则为一个数,`0`表示`+`,`1`表示`*`。 接下来输入$m$行,每行一个数字$c$与编号$k$,表示要求类型为$c$,操作的节点编号为$k$。若$c=1$,那么再输入一个数$V_{i}$表示新的权值。

输出格式


对于每一个$3$操作,请输出一行,该行包括两个数$a$、$b$,分别表示将本节点所在重链的所有节点权值相加**与**相乘的结果。

输入输出样例

输入样例 #1

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

输出样例 #1

18 132
37 360
35 120

说明

对于$30\%$的数据,$1≤n,m≤1000$。 对于$100\%$的数据,$1≤n,m≤10^{6}, 1≤V_{i}<99991$。 **数据保证任何时刻树上没有权值为$0$的节点。**