Description

这些水道形成了一棵以 $1$ 为根的节点数为 $n$ 的树形结构 $T$。每个节点上有一个点权 $w_i$，表示它的危险程度。现做出如下定义：

• 最近公共祖先：在一棵以 $r$ 为根的有根树上，两个节点 $u,v$ 的最近公共祖先，就是这两个点的公共祖先里面，离根最远的那个，记作 $\operatorname{lca}(r,u,v)$。
• 子树：树 $T$ 上，删掉节点 $u$ 与父亲相连的边后，该结点所在的子图记为子树 $T_u$。特别地，$T$ 本身可以认为是以 $1$ 为根节点的子树 $T_1$。
• 危险值：对于 $T_u$ 而言，它的危险值被定义为：

$$\mathrm{LCAS}(u)=\sum_{i\in T_u}\sum_{j\in T_u}\sum_{k\in T_u,k<j} w_{\operatorname{lca}(i,j,k)}$$

现在给出 $T$，希望你对于 $i=1,2,\cdots n$，求出 $\mathrm{LCAS}(i)$。

Input Format

• 第一行有一个正整数 $n$，表示节点的个数。
• 第二行有 $n$ 个整数 $w_i$，表示每个结点的危险程度。
• 接下来 $n-1$ 行，每行有两个正整数 $u,v$，描述 $T$ 中的一条边。

Output Format

• 共 $n$ 行 $n$ 个整数，第 $i$ 个整数表示 $\mathrm{LCAS}(i)$ 的值对 $998,244,353$（一个大质数）取模后的结果。

5
3 1 2 1 3
1 2
1 3
3 4
3 5

109
0
18
0
0

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

972
33
99
0
2
0
0
0
10
0

Hint

样例 1 解释

样例一当中的树如下。红色的是节点，蓝色的是点权。

容易发现 $\mathrm{LCAS}(2)=\mathrm{LCAS}(4)=\mathrm{LCAS}(5)=0$。这里说明如何计算 $\mathrm{LCAS}(1)$ 和 $\mathrm{LCAS}(3)$。首先说明 $\mathrm{LCAS}(3)$：

• 以 $3$ 为根，那么有 $\mathrm{lca}(3,3,4)=\mathrm{lca}(3,3,5)=\mathrm{lca}(3,4,5)=3$，这部分的贡献是 $3\times w_3=6$。
• 以 $4$ 为根，那么有 $\mathrm{lca}(4,3,4)=\mathrm{lca}(4,4,5)=4,\mathrm{lca}(4,3,5)=3$，这部分的贡献是 $2\times w_4+1\times w_3=4$。
• 以 $5$ 为根，那么有 $\mathrm{lca}(5,3,5)=\mathrm{lca}(5,4,5)=5,\mathrm{lca}(5,3,4)=3$，这部分的贡献是 $2\times w_5+1\times w_3=8$。

因此，$\mathrm{LCAS}(3)=6+4+8=18$。下面计算 $\mathrm{LCAS}(1)$。

$$\def\arraystretch{1.2} \begin{matrix} \textbf{以 1 为根 }\bm{\mathbf{lca}(1,i,j)} & \textbf{以 2 为根 }\bm{\mathbf{lca}(2,i,j)}\cr \begin{array}{c||c|c|c|c|c}\hline & 1 & 2 & 3 & 4 & 5 \cr\hline\hline 1 & - & - & - & - &- \cr\hline 2 & 1 & - & - & - &- \cr\hline 3 & 1 & 1 & - & - &- \cr\hline 4 & 1 & 1 & 3 & - &- \cr\hline 5 & 1 & 1 & 3 & 3 &- \cr\hline \end{array} & \begin{array}{c||c|c|c|c|c}\hline & 1 & 2 & 3 & 4 & 5 \cr\hline\hline 1 & - & - & - & - &- \cr\hline 2 & 2 & - & - & - &- \cr\hline 3 & 1 & 2 & - & - &- \cr\hline 4 & 1 & 2 & 3 & - &- \cr\hline 5 & 1 & 2 & 3 & 3 &- \cr\hline \end{array} \cr[50pt] \textbf{以 3 为根 }\bm{\mathbf{lca}(3,i,j)} & \textbf{以 4 为根 }\bm{\mathbf{lca}(4,i,j)}\cr \begin{array}{c||c|c|c|c|c}\hline & 1 & 2 & 3 & 4 & 5 \cr\hline\hline 1 & - & - & - & - &- \cr\hline 2 & 1 & - & - & - &- \cr\hline 3 & 3 & 3 & - & - &- \cr\hline 4 & 3 & 3 & 3 & - &- \cr\hline 5 & 3 & 3 & 3 & 3 &- \cr\hline \end{array} & \begin{array}{c||c|c|c|c|c}\hline & 1 & 2 & 3 & 4 & 5 \cr\hline\hline 1 & - & - & - & - &- \cr\hline 2 & 1 & - & - & - &- \cr\hline 3 & 3 & 3 & - & - &- \cr\hline 4 & 4 & 4 & 4 & - &- \cr\hline 5 & 3 & 3 & 3 & 4 &- \cr\hline \end{array} \end{matrix}\\[10pt] \textbf{以 5 为根 }\bm{\mathbf{lca}(5,i,j)}\\ \begin{array}{c||c|c|c|c|c}\hline & 1 & 2 & 3 & 4 & 5 \cr\hline\hline 1 & - & - & - & - &- \cr\hline 2 & 1 & - & - & - &- \cr\hline 3 & 3 & 3 & - & - &- \cr\hline 4 & 3 & 3 & 3 & - &- \cr\hline 5 & 5 & 5 & 5 & 5 &- \cr\hline \end{array}$$

容易发现，在上图中，$1$ 出现了 $13$ 次，$2$ 出现了 $4$ 次，$3$ 出现了 $25$ 次，$4$ 出现了 $4$ 次，$5$ 出现了 $4$ 次。因此，$\mathrm{LCAS}(1)=3\times 13+1\times 4+2\times 25+1\times 4+3\times 4=109$。

样例 2 解释

我有一个精妙绝伦的方法解释样例 $2$，可惜这里空白太小写不下。

本题输入量较大。请采用较快的读入方式。

数据范围及约定

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|c|}\hline \textbf{Subtask} & \bm{n\le} & \textbf{特殊性质} & \textbf{分值}\cr\hline 1 & 100 & - & 20 \cr\hline 2 & 10^3 & - & 25 \cr\hline 3 & 10^5 & \text{A} & 10\cr\hline 4 & 10^5 & \text{B} & 10\cr\hline 5 & 10^6 & - & 35\cr\hline \end{array}$$

特殊性质 $\textbf{A}$：保证第 $i$ 条边为 $u=i$，$v=i+1$。
特殊性质 $\textbf{B}$：保证第 $i$ 条边为 $u=1$，$v=i+1$。

对于全部数据，保证 $1\le n\le 10^6$，$0\le w_i<998,244,353$。