P7159 "dWoi R1" Sweet Fruit Chocolate.

[Source of the story ...](https://www.bilibili.com/video/BV19Z4y1K7dH) After Toko-mama harmed Yumeno, she wanted to continue her “career” and harm the poor Saihara. She found that Saihara really likes sweet chocolate. There is also something called “Sisyphus fruit”, which is nutritious but not that tasty, so she wants to pour chocolate over the Sisyphus fruit.

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$.

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.

One line containing an integer representing the answer.

#### 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