动态树顶点集路径复合（Dynamic Tree Vertex Set Path Composite）

问题描述

给定一棵含 $N$ 个顶点的树。每条边为 $(u_i, v_i)$，且对每个顶点 $i$，定义一个线性函数 $f_i(x) = a_i x + b_i$。

处理 $Q$ 个查询，类型如下：

• 0 u v w x：删除现有边 $(u, v)$，并添加新边 $(w, x)$（保证操作后图仍为树）。
• 1 p c d：将顶点 $p$ 的函数更新为 $f_p(x) \leftarrow c x + d$。
• 2 u v：设从 $u$ 到 $v$ 的简单路径上的顶点依次为 $p_1 = u, p_2, \dots, p_k = v$，输出$$f_{p_k}(f_{p_{k-1}}(\cdots f_{p_1}(x)\cdots)) \bmod 998244353.$$（注：题面未指定 $x$ 的取值；严格按原文，此处保留表达式形式，实际实现中通常默认计算 $x = 0$ 的结果，但本输出不增补说明。）

约束条件

• $1 \leq N, Q \leq 2 \times 10^5$
• $1 \leq a_i, c < 998244353$
• $0 \leq b_i, d < 998244353$
• $0 \leq p < N$
• $0 \leq u, v < N$
• 对 type 0 查询，$(u, v)$ 是当前树中的一条边
• 图在处理查询过程中始终为树

输入

$N\ Q$
$a_0\ b_0$
$a_1\ b_1$
:
$a_{N-1}\ b_{N-1}$
$u_0\ v_0$
$u_1\ v_1$
:
$u_{N-2}\ v_{N-2}$
Query₀
Query₁
:
Query$_{Q-1}$

输出

对每个类型 2 查询，输出一行：

$$f_{p_k}(f_{p_{k-1}}(\cdots f_{p_1}(x)\cdots)) \bmod 998244353$$

（严格按题面表述，未补充 $x$ 值）

5 7
1 2
3 4
5 6
7 8
9 10
0 1
1 2
2 3
1 4
2 0 3 10
1 1 100000 0
2 3 4 11
0 1 2 2 0
2 3 4 12
0 2 3 3 1
2 2 3 13

1450
387900010
421200010
51100008

#2

7 7
1 2
2 3
3 4
4 5
5 6
6 7
7 8
0 1
1 2
0 3
3 4
0 5
5 6
2 2 4 1
2 4 6 1
2 6 2 1
0 0 5 3 5
2 2 4 1
2 4 6 1
2 6 2 1

411
2199
607
411
2115
2383