Description

b6e0 has a tree. The $i$-th node has value $a_i$. Each edge has length $1$.

b6e0 will choose a node as the root, denoted by $r$. Then, b6e0 will select the entire subtree of some node as his territory, and let the root of this subtree be $u$. At this time, every node in the tree will bring b6e0 some profit. When the root of the territory subtree is $u$, the profit brought by node $x$, denoted by $f(x,u)$, is defined as follows:

1. If $x$ is in the subtree of $u$, then its profit equals the profit of its parent node plus its own value $a_x$.
2. If $x$ is not in the subtree of $u$, then its profit is: among the nodes adjacent to it, take those whose distance to $u$ (the length of the simple path to $u$) is greater than the distance from $x$ to $u$; take the maximum of these nodes' profits modulo $998244353$, and then multiply it by $a_x$.

With root $r$, define the profit of taking $u$ as the subtree, $W(u)$, as the sum of $f$ over all nodes.

Of course, b6e0 has many ways to choose the root. Define the profit when choosing $r$ as the root, $C(r)$, as the sum over all $u$ of the subtree profit $W(u)$. For each node $r$, compute $C(r)$.

---

Formal statement:

You are given a tree with $n$ nodes. The $i$-th node has weight $a_i$, and each edge has length $1$. When the root is $r$:

Let $F(x)$ denote the parent of $x$. In particular, $F(r)=0$. Let $D(x,y)$ denote the length of the simple path from $x$ to $y$. In particular, for all $x$, $D(x,x)=0$. Let $A_x$ denote the set of nodes in the subtree of $x$ (including $x$ itself), i.e. $A_x=\{y\mid D(x,y)=D(F(x),y)-1\}$. In particular, $A_r=\{1,2,\cdots,n\}$. Let $B_x$ denote the set of nodes adjacent to $x$, i.e. $B_x=\{y\mid D(x,y)=1\}$.

Define $f(x,u)$:

$$f(x,u)=\begin{cases}f(F(x),u)+a_x&x\in A_u\\a_x\cdot\max_{y\in B_x,D(y,u)>D(x,u)}\{f(y,u)\bmod 998244353\}&x\not\in A_u\end{cases}$$

In particular, for all $x$, $f(0,x)=0$. In the case $x\not\in A_u$, if for all $y\in B_x$ we have $D(y,u)\le D(x,u)$, then $f(x,u)=a_x$.

Define the score of node $u$ as $W(u)=\sum_{v=1}^nf(v,u)$.

Define the profit of node $r$, $C(r)$, as the value of $\sum_{i=1}^nW(i)$ when the root is $r$.

For each node $r$, compute $C(r)$.

All $C(r)$ are taken modulo $998244353$.

Input Format

The first line contains a positive integer $n$, the number of nodes in the tree.

The second line contains $n$ integers. The $i$-th integer denotes the node weight $a_i$ of node $i$.

The next $n-1$ lines each contain two positive integers $u,v$, indicating that there is an edge between node $u$ and node $v$.

Output Format

Output $n$ lines. The $i$-th line outputs a positive integer, the value of node $i$'s profit $C(i)$ modulo $998244353$.

6
7 2 5 100 1 5
1 3
3 4
1 2
4 5
4 6

67562
29930
75168
76888
63243
63283

Hint

[Sample Explanation]

The tree in the sample is shown in the figure:

For example, when $r=1$ and $u=5$, $f(2,u)=a_2=2$, $f(1,u)=a_1\cdot f(2,u)=14$, $f(3,u)=a_3\cdot f(1,u)=70$, $f(6,u)=a_6=5$, $f(4,u)=a_4\cdot\max\{f(3,u),f(6,u)\}=7000$, and $f(5,u)=f(4,u)+a_5=7001$.

[Constraints]

• Subtask 1 (10 pts): $n\le200$, $a_i\le 10^3$.
• Subtask 2 (20 pts): $n\le10^3$.
• Subtask 3 (20 pts): the tree is a chain.
• Subtask 4 (20 pts): there exists a node whose degree is $n-1$.
• Subtask 5 (30 pts): no special restrictions.

For $100\%$ of the testdata, $1\le n\le5\times10^5$, $1\le a_i\le10^9$.

Translated by ChatGPT 5