U361349 Vertex Set Path Composite

Reprinted from [USACO](https://judge.yosupo.jp/problem/vertex_set_path_composite).

Given an N vertices tree. Edges are $(u_{i},v_{i})$ and a linear function $f_{i}(x)=a_{i}x+b_{i}$ is written on the vertex $i$ for each $i$. Process $Q$ queries as follows: - $0$ $p$ $c$ $d$: Set $f_{p} \gets cx + d$ - 1 u v x: Let vertices on the path between $u$ and $v$ be $p_{1} = u, p_{2},..., p_{k} = v$. Print $f_{p_{k}}(...f_{p_{2}}(f_{p_{1}}(x)))$ mod 998244353

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

无

- 1≤$N,Q$≤200000 - 1≤$a_{i},c$