单点赋值树路径复合和

【题目描述】

给定

• 一棵有 $N$ 个顶点的树，
• $N$ 个整数 $a _ 0, a _ 1, \ldots, a _ {N-1}$，
• $N-1$ 个整数 $b _ 0, b _ 1, \ldots, b _ {N-2}$，以及
• $N-1$ 个整数 $c _ 0, c _ 1, \ldots, c _ {N-2}$。

边 $i$ 双向连接顶点 $u _ i$ 和 $v _ i$。

对于满足 $0 \leq e \leq N-2$ 的整数 $e$，令 $f _ e(x) = b _ e x + c _ e$。

令 $e _ 0, e _ 1, \ldots, e _ k$ 为从顶点 $x$ 到顶点 $y$ 的简单路径上按顺序排列的边，并定义 $P(x, y) = f _ {e _ 0}(f _ {e _ 1}(\ldots f _ {e _ k}(a _ y) \ldots ))$。

按给定顺序处理 $Q$ 个查询。查询有两种类型：

• 0 w x r：将 $a_w$ 更新为 $x$，然后输出 $\left(\sum_{v=0}^{N-1} P(r, v)\right) \bmod 998244353$。
• 1 e y z r：将 $(b_e, c_e)$ 更新为 $(y, z)$，然后输出 $\left(\sum_{v=0}^{N-1} P(r, v)\right) \bmod 998244353$。

【输入】

输入格式如下，其中 $\mathrm{Query}_i$ 表示第 $i$ 个查询。

$N$ $Q$
$a _ 0$ $a _ 1$ $\ldots$ $a _ {N-1}$
$u _ 0$ $v _ 0$ $b _ 0$ $c _ 0$
$u _ 1$ $v _ 1$ $b _ 1$ $c _ 1$
$\vdots$
$u _ {N-2}$ $v _ {N-2}$ $b _ {N-2}$ $c _ {N-2}$
$\mathrm{Query}_0$
$\mathrm{Query}_1$
$\vdots$
$\mathrm{Query}_{Q-1}$

【输出】

记 $p_i$ 为第 $i$ 个查询的答案，输出格式如下。

$p_0$
$p_1$ 
$\vdots$
$p_{Q-1}$

【输入样例】

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

【输出样例】

239
76

【输入样例2】

8 4
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 5
1 4 100000 2 2
0 7 100000 3
0 0 100000 0

【输出样例2】

5161
175810713
702319900
769103076

【数据范围】

• 所有输入均为整数。
• $1 \leq N \leq 200000$
• $1 \leq Q \leq 200000$
• $0 \leq u _ i, v _ i \leq N - 1$
• $0 \leq a _ w \lt 998244353$
• $1 \leq b _ e \lt 998244353$
• $0 \leq c _ e \lt 998244353$
• $0 \leq w \leq N - 1$
• $0 \leq e \leq N - 2$
• $0 \leq x \lt 998244353$
• $1 \leq y \lt 998244353$
• $0 \leq z \lt 998244353$
• $0 \leq r \leq N - 1$

【来源】

Library Checker（yosupo06） point_set_tree_path_composite_sum