Description

Tojo makes the chocolate she wants to pour into a “chocolate fountain tree”. The chocolate fountain tree is a tree with $n$ nodes. Each node has a Sisyphus fruit. For each node $u$, you have two choices: you can place $a_u$ fruits at node $u$, or place no fruit at all. Then, Tojo will pour chocolate syrup from the root downward. The nutrition value that node $u$ brings to Saihara is the number of Sisyphus fruits placed in $u$ and its subtree. Tojo wants to know, among all $2^n$ fruit-placement plans, what is the total sum of Saihara’s nutrition values. Output the answer modulo $998244353$.

The root of the tree is node $1$.

Input Format

The first line contains a positive integer $n$.

The second line contains $n$ positive integers $a_i$.

In the next $n - 1$ lines, each line contains two positive integers $u, v$ $(1\le u, v\le n)$, indicating that there is an edge $(u, v)$ in the tree.

Output Format

One line containing an integer representing the answer.

3
1 1 2
1 2
2 3

36

Hint

Sample 1 Explanation

Use $S$ to represent the selected state.

• $S = 000$ contributes $0$.
• $S = 001$ contributes $1$.
• $S = 010$ contributes $2$.
• $S = 011$ contributes $3$.
• $S = 100$ contributes $6$.
• $S = 101$ contributes $7$.
• $S = 110$ contributes $8$.
• $S = 111$ contributes $9$.

Constraints

For $20\%$ of the testdata, $n \le 20$.

For another $30\%$ of the testdata, $u = v - 1$.

For $100\%$ of the testdata, $2 \le n \le 10^6$, $1 \le a_i \le 10^9$.

Translated by ChatGPT 5