Background

Murasa Minamitsu is the captain who controls the Hijiri ship. As a ship ghost who has spent her whole life with ships, she is very interested in them. Because of this hobby, Murasa has a lot of ship models.

Due to the eruption of a geyser, a large water pit appeared around it, gathering many streams of water. Different streams interweave and form waterways of various sizes. If you just place a ship model at some position, it will flow along the water. According to physics, a ship naturally flows from high places to low places. Since the pit is formed by water gathering from all directions, the center of the pit is the lowest; as the distance to the center increases, the terrain keeps getting higher.

Murasa found that when she chooses two positions to place ship models, they will collide at some junction of the waterways. Murasa cares about where the collision happens. It is easy to see that the first possible collision position is the lowest common ancestor of the two chosen points in the tree structure.

Of course, since the geyser is unstable, the position of the center of the pool may keep changing, and the terrain also changes, but the waterways do not change at all. Murasa labels each junction with a value called "danger level", representing how dangerous it might be if two ship models collide there. The positions where Murasa places ship models are also random.

However, the pit is too large, and the center keeps changing, so Murasa, who only cares about ship models, gets confused. She urgently wants to know the threat caused by playing with ship models in the pit, so she hopes you can help her compute it.

Problem Description

These waterways form a rooted tree structure $T$ with $n$ nodes, rooted at $1$. Each node has a node weight $w_i$, representing its danger level. Define the following:

• Lowest common ancestor: In a rooted tree with root $r$, the lowest common ancestor of two nodes $u,v$ is the common ancestor of these two nodes that is farthest from the root, denoted as $\operatorname{lca}(r,u,v)$.
• Subtree: In tree $T$, after deleting the edge between node $u$ and its parent, the connected component containing $u$ is called the subtree $T_u$. In particular, $T$ itself can be seen as the subtree $T_1$ rooted at $1$.
• Danger value: For $T_u$, its danger value is defined as:

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

Now given $T$, for $i=1,2,\cdots n$, compute $\mathrm{LCAS}(i)$.

Input Format

• The first line contains a positive integer $n$, the number of nodes.
• The second line contains $n$ integers $w_i$, the danger level of each node.
• The next $n-1$ lines each contain two positive integers $u,v$, describing an edge in $T$.

Output Format

• Output $n$ lines, each containing one integer. The $i$-th integer is $\mathrm{LCAS}(i)\bmod 998,244,353$ (a large prime).

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

Explanation for Sample 1

The tree in sample 1 is as follows. Red nodes are the nodes, and blue ones are the node weights.

It is easy to see that $\mathrm{LCAS}(2)=\mathrm{LCAS}(4)=\mathrm{LCAS}(5)=0$. Here we explain how to compute $\mathrm{LCAS}(1)$ and $\mathrm{LCAS}(3)$. First, we explain $\mathrm{LCAS}(3)$:

• With $3$ as the root, we have $\mathrm{lca}(3,3,4)=\mathrm{lca}(3,3,5)=\mathrm{lca}(3,4,5)=3$, and the contribution of this part is $3\times w_3=6$.
• With $4$ as the root, we have $\mathrm{lca}(4,3,4)=\mathrm{lca}(4,4,5)=4,\mathrm{lca}(4,3,5)=3$, and the contribution of this part is $2\times w_4+1\times w_3=4$.
• With $5$ as the root, we have $\mathrm{lca}(5,3,5)=\mathrm{lca}(5,4,5)=5,\mathrm{lca}(5,3,4)=3$, and the contribution of this part is $2\times w_5+1\times w_3=8$.

Therefore, $\mathrm{LCAS}(3)=6+4+8=18$. Next we compute $\mathrm{LCAS}(1)$.

$$\def\arraystretch{1.2} \begin{matrix} \textbf{Root is 1 }\bm{\mathbf{lca}(1,i,j)} & \textbf{Root is 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{Root is 3 }\bm{\mathbf{lca}(3,i,j)} & \textbf{Root is 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{Root is 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}$$

It is easy to see that in the table above, $1$ appears $13$ times, $2$ appears $4$ times, $3$ appears $25$ times, $4$ appears $4$ times, and $5$ appears $4$ times. Therefore, $\mathrm{LCAS}(1)=3\times 13+1\times 4+2\times 25+1\times 4+3\times 4=109$.

Explanation for Sample 2

I have an ingenious method to explain sample $2$, but unfortunately this blank area is too small to write it down.

The input size of this problem is large. Please use a fast input method.

Constraints and Notes

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|c|}\hline \textbf{Subtask} & \bm{n\le} & \textbf{Special Property} & \textbf{Score}\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}$$

Special Property $\textbf{A}$: It is guaranteed that the $i$-th edge is $u=i$, $v=i+1$.
Special Property $\textbf{B}$: It is guaranteed that the $i$-th edge is $u=1$, $v=i+1$.

For all testdata, it is guaranteed that $1\le n\le 10^6$ and $0\le w_i<998,244,353$.

Translated by ChatGPT 5