顶点赋值路径复合（Vertex Set Path Composite）

问题描述

给定一棵含 $N$ 个顶点的树，边为 $(u_i, v_i)$。对每个顶点 $i$，初始关联一个线性函数 $f_i(x) = a_i x + b_i$。
请按顺序处理以下 $Q$ 个查询：

• 0 p c d：将顶点 $p$ 关联的函数更新为 $f_p(x) \leftarrow c x + d$。
• 1 u v x：设从 $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.$$

约束条件

• $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$

输入格式

$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_0$
$Query_1$
:
$Query_{Q-1}$

5 5
1 2
3 4
5 6
7 8
9 10
0 1
1 2
2 3
2 4
1 0 3 11
1 2 4 12
0 2 13 14
1 0 4 15
1 2 2 16

1555
604
6571
222

#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
1 2 4 1
1 4 6 1
1 6 2 1
0 1 20 30
1 2 4 1
1 4 6 1
1 6 2 1

411
2199
607
3471
2199
6034