AT_scpc2026_div1_l Lulu, the Magician

Lulu 实际上是一位天才魔法师。经过长时间的研究，Lulu 利用魔法阵开发出了属于自己的秘密魔法。 Lulu 使用的魔法阵是一棵包含 $N$ 个咒语和 $N-1$ 条连接的树结构。咒语按顺序编号为 $1$ 到 $N$，Lulu 可以为每个咒语进行强化。魔法阵中的第 $i$ 条连接表示咒语 $a_i$ 和咒语 $b_i$ 直接连接。 初始时，每个咒语的能量为 $0$。当 Lulu 将第 $r$ 个咒语强化 $w$ 点时，第 $r$ 个咒语的能量 $W_r$ 增加 $w$。 Lulu 可以选择魔法阵中的两个咒语 $u$ 和 $v$ 施展魔法。施展魔法时，魔法阵中的每个咒语都会与 $P(u, v)$ 集合中的所有点产生作用，其中 $P(u, v)$ 表示连接 $u$ 和 $v$ 的唯一一条简单路径上的结点集合。Lulu 施展的魔法最终能量可以按如下公式计算。这里 $d(a,b)$ 表示从 $a$ 到 $b$ 的唯一一条简单路径上的边数： $$ \sum_{x \in P(u, v)} \sum_{r=1}^{N} W_r \times d(r, x) $$ 天才魔法师 Lulu 想要通过以下两种操作（共 $Q$ 次，按顺序进行）进行魔法的学习： - `1 v w`：将第 $v$ 个咒语的能量增加 $w$。 - `2 u v`：选择咒语 $u$ 和 $v$，施展一次魔法。 对于每个类型为 $2$ 的操作，请输出施展的魔法最终能量对 $998\,244\,353$ 取模的结果。

输入格式如下： > $N$ $Q$ $a_1$ $b_1$ $a_2$ $b_2$ $\vdots$ $a_{N-1}$ $b_{N-1}$ $\mathrm{action}_1$ $\mathrm{action}_2$ $\vdots$ $\mathrm{action}_Q$

对于每个类型为 $2$ 的操作，输出一行，表示所施展魔法的最终能量对 $998\,244\,353$ 取模后的结果。

### 数据范围 - $1 \leq N, Q \leq 200\,000$ - $1 \leq a_i, b_i \leq N$ - $a_i \ne b_i$ - 给定的魔法阵是一棵树。 - 对于操作 `1 v w`，有 $1 \leq v \leq N$，$1 \leq w \leq 10^9$。 - 对于操作 `2 u v`，有 $1 \leq u, v \leq N$。 - 所有输入均为整数。 由 ChatGPT 5 翻译