在 A 国,小 B 掌握了一种用于精确预测天气的技术。
小 B 的预测技术依赖于一台机器,它是一个 n 个节点的树,根是 1,每个节点有偶数个儿子。对于每个节点,有两个数据:采集数据与分析数据。
每天,小 B 会从自然界采集 n 项数据,每项数据是 0 或 1,其中第 i 项数据会载入机器中第 i 个节点的采集数据。
当数据收集完毕时,小 B 会开启机器进行计算分析数据的内容:每个节点分析数据将载入它所有儿子的分析数据与它自己的采集数据的众数。
当计算完毕后,最终如果树根节点的分析数据为 1,那么明天会下雨,不然明天不下雨。
但是不幸的是,有时候采集数据的工作并不是那么简单,对此,小 B 给出了他对这些数据的预估:第 i 项数据为 1 的概率是 pi,并且所有数据的分布独立。对此,小 B 希望你帮他快速计算明天下雨的概率。当然,小 B 有时候会对一些数据进行更新,他会每次告诉你一项数据的概率发生了改变,你也需要给出每次改变后的答案。你只需要给出答案对 998244353 取模的结果。
Input
第一行两个整数 n,q,表示树的点数以及修改个数。
下面一行 n−1 个正整数,其中第 i 个正整数 anci+1 表示节点 i+1 的父亲。
下面一行 n 个整数 wi,一开始的 pi=wi998244354。
下面 q 行,每行两个整数 posi,vi,表示将 pposi 改为 vi998244354。
Output
一共 q+1 行,每行一个整数表示一开始与每次修改后的答案对 998244353 取模的结果。
Examples
Input 1
3 1 1 1 499122177 499122177 499122177 1 0
Output 1
499122177 748683265
Input 2
5 3 1 1 2 2 332748118 1 332748118 499122177 499122177 2 332748118 1 1 1 332748118
Output 2
776412275 850356301 942786334 850356301
Scoring
对于所有数据:1≤n≤200000, 1≤q≤50000,且每个节点儿子个数为偶数。
0≤wi,vi≤998244353
子任务编号 | n≤ | q≤ | 特殊性质 | 分值 |
---|---|---|---|---|
1 | n≤100 | q≤100 | 无 | 12 |
2 | n≤200000 | q≤50000 | A | 20 |
3 | B | 20 | ||
4 | C | 23 | ||
5 | 无 | 25 |
性质 A: anc2i=anc2i+1,且在 [1,2i−1] 中均匀随机生成。
性质 B: 每个节点儿子个数不超过 10
性质 C: anci=1