树路径复合和（Tree Path Composite Sum）

问题描述

给你一棵含 $N$ 个顶点的树，以及以下输入：

• 整数序列 $a_0, a_1, \dots, a_{N-1}$；
• $N-1$ 条边，第 $i$ 条边连接顶点 $u_i$ 和 $v_i$，并关联参数 $b_i, c_i$；
• 对每个边索引 $e$（$0 \le e \le N-2$），定义线性函数 $f_e(x) = b_e x + c_e$。

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

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

请对每个顶点 $x$，计算

$$q_x = \sum_{y=0}^{N-1} P(x, y) \bmod 998244353.$$

约束条件

• 所有输入均为整数。
• $1 \leq N \leq 2 \times 10^5$
• $0 \leq u_i, v_i \leq N-1$
• $0 \leq a_i < 998244353$
• $1 \leq b_i < 998244353$
• $0 \leq c_i < 998244353$

输入格式

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

输出格式

$q_0\ q_1\ \cdots\ q_{N-1}$

8
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

9287 89589 895590 92471 92375 5131 42598 425185

3
1 100 10000
0 1 100000 0
1 2 100000 0

881938226 1855747 27566470