Migrated from Lutece 3003 又是树上距离

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

给一棵 $n$ 个点的树，每个点 $i$ 有点权 $a_i$ 。定义两个点 $i,j$ 之间的花费 $cost(i,j)$ 为 $a_i\cdot a_j\cdot dis^2(i,j)$，其中 $dis(i,j)$ 表示节点 $i,j$ 在树上的距离。现在你需要对每个点 $i$ 求$(\sum_{j=1}^n cost(i,j))\mod 998244353$ 的值。

Input

第一行一个正整数 $n$，表示树的节点个数。 第二行 $n$ 个正整数 $a_1,a_2,\cdots,a_n$，表示每个点的点权。 接下来 $n-1$ 行，每行两个整数$u_i,v_i(1\le u_i,v_i\le n,u_i\neq v_i)$，表示点$u_i,v_i$之间有一条边。

Output

输出 $n$ 行，第 $i$ 行表示第 $i$ 个数的答案。

Samples

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

35
56
201
252
360

Constraints

$2\le n\le 10^5$,$1\le a_i\le10^9$

Note

对于样例中的3号节点，其距离1,2,3,4,5号节点的距离分别为 $2,1,0,2,3$，因此对应的答案为 $3\times 1\times 2^2+3\times 2\times 1^2+3\times 3\times 0^2+3\times 4\times 2^2+3\times 5\times 3^2=12+6+0+48+135=201$.

Resources

2023 UESTC ICPC Training for Search and Dynamic Programming