11272: [yosupo] Tree - Point Set Tree Path Composite Sum
[Creator : ]
Description
You are given
- a tree with $N$ vertices,
- $N$ integers $a _ 0, a _ 1, \ldots, a _ {N-1}$ ,
- $N-1$ integers $b _ 0, b _ 1, \ldots, b _ {N-2}$ , and
- $N-1$ integers $c _ 0, c _ 1, \ldots, c _ {N-2}$ .
Edge $i$ connects vertices $u _ i$ and $v _ i$ bidirectionally.
For an integer $e$ that satisfies $0 \leq e \leq N-2$ , let $f _ e(x) = b _ e x + c _ e$ .
Let $e _ 0, e _ 1, \ldots, e _ k$ be the edges on the simple path from vertex $x$ to vertex $y$ in order, and define $P(x, y) = f _ {e _ 0}(f _ {e _ 1}(\ldots f _ {e _ k}(a _ y) \ldots ))$ .
Process $Q$ queries in the order they are given. There are two types of queries:
- `0 w x r` : Update $a_w$ to $x$ and then print $\left(\sum_{v=0}^{N-1} P(r, v)\right) \bmod 998244353$.
- `1 e y z r` : Update $(b_e, c_e)$ to $(y, z)$ and then print $\left(\sum_{v=0}^{N-1} P(r, v)\right) \bmod 998244353$.
- a tree with $N$ vertices,
- $N$ integers $a _ 0, a _ 1, \ldots, a _ {N-1}$ ,
- $N-1$ integers $b _ 0, b _ 1, \ldots, b _ {N-2}$ , and
- $N-1$ integers $c _ 0, c _ 1, \ldots, c _ {N-2}$ .
Edge $i$ connects vertices $u _ i$ and $v _ i$ bidirectionally.
For an integer $e$ that satisfies $0 \leq e \leq N-2$ , let $f _ e(x) = b _ e x + c _ e$ .
Let $e _ 0, e _ 1, \ldots, e _ k$ be the edges on the simple path from vertex $x$ to vertex $y$ in order, and define $P(x, y) = f _ {e _ 0}(f _ {e _ 1}(\ldots f _ {e _ k}(a _ y) \ldots ))$ .
Process $Q$ queries in the order they are given. There are two types of queries:
- `0 w x r` : Update $a_w$ to $x$ and then print $\left(\sum_{v=0}^{N-1} P(r, v)\right) \bmod 998244353$.
- `1 e y z r` : Update $(b_e, c_e)$ to $(y, z)$ and then print $\left(\sum_{v=0}^{N-1} P(r, v)\right) \bmod 998244353$.
Input
$\mathrm{Query}_i$ represents the $i$-th query.
$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}$
$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}$
Output
$p_i$ represents the answer to the $i$-th query.
$p_0$
$p_1$
$\vdots$
$p_{Q-1}$
$p_0$
$p_1$
$\vdots$
$p_{Q-1}$
Constraints
- All input are integers.
- $1 \leq N \leq 2\times 10^5$
- $1 \leq Q \leq 2\times 10^5$
- $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$
- $1 \leq N \leq 2\times 10^5$
- $1 \leq Q \leq 2\times 10^5$
- $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$
Sample 1 Input
3 2
1 2 3
0 1 4 5
1 2 6 7
0 2 8 0
1 0 9 10 1
Sample 1 Output
239
76
Sample 2 Input
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
Sample 2 Output
5161
175810713
702319900
769103076