树上点修 & 路径复合求和（固定根）

（Point Set Tree Path Composite Sum (Fixed Root)）

问题描述

给定：

• 一棵含 $N$ 个顶点的树；
• $N$ 个整数 $a_0, a_1, \dots, a_{N-1}$；
• $N-1$ 个整数 $b_0, b_1, \dots, b_{N-2}$；
• $N-1$ 个整数 $c_0, c_1, \dots, c_{N-2}$。

其中第 $e$ 条边（$0 \le e \le N-2$）连接顶点 $u_e$ 和 $v_e$，且为无向边。

对每个 $e$（$0 \le e \le N-2$），定义线性函数

$$f_e(x) = b_e \cdot x + c_e.$$

对任意顶点 $y$，设 $e_0, e_1, \dots, e_k$ 是从顶点 0 到顶点 $y$ 的简单路径上的边（按从 0 到 $y$ 的顺序），定义复合函数

$$P(y) = f_{e_k}(f_{e_{k-1}}(\cdots f_{e_0}(a_y)\cdots)).$$

处理 $Q$ 个查询：

• 0 w x：将 $a_w$ 更新为 $x$，然后输出 $\sum_{v=0}^{N-1} P(v) \bmod 998244353$。
• 1 y z：将边 $e_y$ 的参数更新为 $(b_y, c_y) \leftarrow (z, c_y)$（即仅更新 $b_y$ 为 $z$），然后输出 $\sum_{v=0}^{N-1} P(v) \bmod 998244353$。

约束条件

• 所有输入均为整数。
• $1 \leq N \leq 2 \times 10^5$
• $1 \leq Q \leq 2 \times 10^5$
• $0 \leq u_e, v_e \leq N-1$
• $0 \leq a_w < 998244353$
• $1 \leq b_e < 998244353$
• $0 \leq c_e < 998244353$
• $0 \leq w \leq N-1$
• $0 \leq e \leq N-2$
• $0 \leq x < 998244353$
• $1 \leq y \leq N-2$
• $1 \leq z < 998244353$

输入

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

输出

$p_0$
$p_1$
:
$p_{Q-1}$

其中 $p_i$ 表示第 $i$ 个查询的答案。

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

239
534

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

9587
91600430
769003077