P5499 [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$。

无

无

对于$30\%$的数据，$1≤n,m≤1000$。 对于$100\%$的数据，$1≤n,m≤10^{6}, 1≤V_{i}