U486821 原(link)

世界树上最纯净的枝丫，纳西妲，最近发现世界树被禁忌知识污染了。 对于世界树上的每一条树边，都有一定概率被污染。同时，世界树也在不断生长，但即使是新生长的枝丫，也抵不过禁忌知识的侵蚀。 纳西妲只可以存在于纯净区域，所谓纯净区域，就是一个世界树上的连通的一部分，且不含被污染的树边。 一个极大的纯净区域是一个世界树的纯净区域，且无法再包含更多的树边或树的分叉点。 纳西妲的神力还很弱，无法净化被污染的区域，于是她只能暂时停留在极大纯净区域。

给定一棵树，每条边都有一个被割掉的概率 $p_i$。 一开始树是完整的。现在有一把刀，对于每一条树边，都有 $p_i$ 的概率割掉。 定义 $P(i)$ 为最终连通块数量为 $i$ 的概率。 现在要你求 $\sum\limits_{i=1}^{n}P(i)\times i$ 的值，对 $998244353$ 取模。其中 $n$ 是**当前**树的节点数量。 同时，树的形态会发生改变，你需要动态询问，询问**不**互相独立。

第一行两个整数 $n,t$ 表示树的节点个数和输入参数。 接下来 $n-1$ 行，每行四个非负整数 $u,v,a,b$ 表示一条连接节点 $u,v$ 的边，被割掉的概率为 $\frac ab$。 接下来一个数 $m$ 表示询问总数。 接下来 $m$ 行，每行三个数 $v',a',b'$ 表示一组询问，第 $i$ 个询问表示新增一条边 $(i+n,v)$，被割的概率为 $\frac ab$。注意，此处的 $v',a',b'$ 均为加密后的结果，为了解密，你需要对他们进行操作。若 $t=0$ 则不需要额外操作，即 $v=v',a=a',b=b'$；若 $t=1$，你需要将它们异或上 $lstans$，即 $v=v'\oplus lstans,a=a'\oplus lstans,b=b'\oplus lstans$，其中 $lstans$ 为上一次询问的答案，第一次询问时 $lstans$ 为初始树的询问的答案。数据保证任何时刻都是一棵树。 对于每一组 $a,b$，不保证 $\gcd(a,b)=1$，但保证 $b\neq 0,\frac ab \in [0,1],a,b\in[1,998244352]$。

首选你需要先求出包括初始树和 $m$ 个附加询问一共 $m+1$ 个询问的答案，记为 $a_{[0,m]}$。注意此处的 $a$ 是对 $998244353$ 取模后的结果。 定义 $b=\oplus_{i=0}^m(i+a_i)$，注意此处**不需要**对 $998244353$ 取模。 输出一行一个整数 $b$。

样例 $1$ 解释： 初始询问 $P(1)=0,P(2)=1,ans=2$。 加入边之后，$P(1)=0,P(2)=\frac 13,P(3)=\frac 23,ans=\frac 83\equiv665496238$。 你应该输出 $(0+2)\oplus(1+665496238)=665496237$。 | 数据点编号 | $n\leqslant$ | $m\leqslant $ | $t=$ | 特殊性质 | | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | | $1\sim3$ | $5$ | $5$ | $1$ | | | $4\sim6$ | $17$ | $5$ | $1$ | | | $7\sim10$ | $3\times10^3$ | $10^3$ | $0$ | | | $11\sim12$ | $3\times10^3$ | $3\times10^3$ | $1$ | | | $13\sim14$ | $2\times10^5$ | $0$ | $0$ | $\tt A$ | | $15\sim17$ | $2\times10^5$ | $2\times10^5$ | $0$ | | | $18\sim20$ | $2\times10^5$ | $2\times10^5$ | $1$ | | 性质 $\tt A$：保证第 $i$ 条边连接的是节点 $i$ 和 $i+1$。