Tree Territory Profit Re-rooting

You are given an undirected tree with n nodes, where the i-th node has a weight a_i. Every edge has length 1. For any choice of a root node r, we define a parent array F and the subtree A_x for each node x as follows:

• For r, define F(r)=0 and A_r = {1,2,...,n}.
• For any other node x with F(x) as its parent (determined in the tree rooted at r), A_x is the set of nodes in the subtree of x (including x itself), i.e. A_x = {y | D(x,y)=D(F(x),y)-1}.

Now, fix a root r and consider any node u (which will serve as the root of a territory). For every node x in the tree, define its profit f(x,u) with respect to territory root u as follows:

$$ f(x,u)=\begin{cases} f(F(x),u)+a_x, & \text{if } x\in A_u,\\[6mm] a_x\cdot\max\{f(y,u) \bmod 998244353 \mid y\in B_x,\;D(y,u)>D(x,u)\}, & \text{if } x\not\in A_u,\\[4mm] \text{and if } \{y\in B_x: D(y,u)>D(x,u)\}=\emptyset \text{ then } f(x,u)=a_x. \end{cases} $$

Here,

• F(x) is the parent of x in the tree rooted at r (with the convention that F(r)=0 and f(0,u)=0 for any u).
• D(x,y) is the length of the unique simple path between x and y (with D(x,x)=0).
• B_x is the set of nodes adjacent to x.

Define the territory profit of u as

$$W(u)=\sum_{x=1}^n f(x,u).$$

Finally, define the profit C(r) when choosing r as the root to be

$$C(r)=\sum_{u=1}^n W(u).$$

Your task is: for every node r (from 1 to n), compute C(r) modulo 998244353.

Note: The computations in the second case of the recurrence use the value of f(y,u) modulo 998244353 before taking the maximum.

---

Explanation: For a fixed root r, the tree has a well defined parent-child structure. For each possible territory root u, nodes in the subtree of u (with respect to this structure) have their profit computed additively along the chain from u (with f(u,u)=a_u), while for nodes outside that subtree the profit depends on the maximum profit (modulo 998244353) among adjacent nodes that are further from u (if any exist; otherwise it is simply a_x).

inputFormat

The first line contains an integer n (the number of nodes).

The second line contains n integers: a₁, a₂, ..., a_n.

Each of the next n−1 lines contains two integers u and v describing an edge between nodes u and v.

outputFormat

Output n space‐separated integers where the r-th integer is C(r) modulo 998244353.

sample

3
1 2 3
1 2
2 3

29 28 27

</p>