Hanh 是一位著名的生物学家。他喜欢在自己的花园里种树和做实验。
有一天,他得到了一棵由 $$$n$$$ 个顶点组成的树。顶点编号从 $$$1$$$ 到 $$$n$$$。具有 $$$n$$$ 顶点的树是具有 $$$n-1$$$ 边的无向连通图。最初,Hanh 将每个顶点的值设置为 $$$0$$$。
现在,Hanh 执行 $$$q$$$ 操作,每个操作都是以下类型之一:
- 输入 $$$1$$$:Hanh 选择顶点 $$$v$$$ 和整数 $$$d$$$。然后他均匀地随机选择一些顶点$$$r$$$,列出所有顶点$$$u$$$,使得从$$$r$$$到$$$u$$$的路径经过$$$v$$$。然后 Hanh 将所有这些顶点 $$$u$$$ 的值增加 $$$d$$$。
- 输入 $$$2$$$:Hanh 选择顶点 $$$v$$$ 并计算 $$$v$$$ 的期望值。
由于 Hanh 擅长生物学但不擅长数学,因此他需要你在这些操作上提供帮助。
输入
第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \leq n, q \leq 150\,000$$$) - Hanh 树上的顶点数和他执行的操作数。
接下来的 $$$n - 1$$$ 行中的每一行都包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \leq u, v \leq n$$$),表示有一条边连接两个顶点 $$$u$$$ 和 $$$v$$$。保证这些 $$$n - 1$$$ 边形成一棵树。
最后 $$$q$$$ 行以任一格式描述操作:
- $$$1$$$ $$$v$$$ $$$d$$$ ($$$1 \leq v \leq n, 0 \leq d \leq 10^7$$$),表示第一类操作。
- $$$2$$$ $$$v$$$ ($$$1 \leq v \leq n$$$),表示第二种操作。
保证至少有一个第二类型的查询。
输出
对于第二种类型的每个操作,将期望值写在一行上。
令$$$M = 998244353$$$,可以证明期望值可以表示为不可约分数$$$\frac{p}{q}$$$,其中$$$p$$$和$$$q$$$是整数,并且$$$q \not \equiv 0 \pmod{M}$$$。输出等于 $$$p \cdot q^{-1} \bmod M$$$ 的整数。换句话说,输出一个整数$$$x$$$,使得$$$0 \le x < M$$$ 且$$$x \cdot q \equiv p \pmod{M}$$$。
示例
输入 #1
5 12 1 2 1 3 2 4 2 5 1 1 1 2 1 2 2 2 3 2 4 2 5 1 2 2 2 1 2 2 2 3 2 4 2 5
输出 #1
1 199648871 399297742 199648871 199648871 598946614 199648873 2 2 2
注意
下图显示了示例中的树:
对于第一个查询,其中 $$$v = 1$$$ 且 $$$d = 1$$$:
- 如果 $$$r = 1$$$,则所有顶点的值都会增加。
- 如果 $$$r = 2$$$,则顶点 $$$1$$$ 和 $$$3$$$ 的值会增加。
- 如果 $$$r = 3$$$,则顶点 $$$1$$$、$$$2$$$、$$$4$$$ 和 $$$5$$$ 的值会增加。
- 如果 $$$r = 4$$$,则顶点 $$$1$$$ 和 $$$3$$$ 的值会增加。
- 如果 $$$r = 5$$$,则顶点 $$$1$$$ 和 $$$3$$$ 的值会增加。
因此,此查询后所有顶点的期望值为 ($$$1, 0.4, 0.8, 0.4, 0.4$$$)。
对于第二个查询,其中 $$$v = 2$$$ 且 $$$d = 2$$$:
- 如果 $$$r = 1$$$,则顶点 $$$2$$$、$$$4$$$ 和 $$$5$$$ 的值会增加。
- 如果 $$$r = 2$$$,则所有顶点的值都会增加。
- 如果 $$$r = 3$$$,则顶点 $$$2$$$、$$$4$$$ 和 $$$5$$$ 的值会增加。
- 如果 $$$r = 4$$$,则顶点 $$$1$$$、$$$2$$$、$$$3$$$ 和 $$$5$$$ 的值会增加。
- 如果 $$$r = 5$$$,则顶点 $$$1$$$、$$$2$$$、$$$3$$$ 和 $$$4$$$ 的值会增加。
因此,此查询后所有顶点的期望值为 ($$$2.2, 2.4, 2, 2, 2$$$)。