Background

Maybe the sun won't shine
Maybe the rain won't fall
But maybe our love will find a way
And rise above it all
Maybe there comes a day
When all of the skies turn grey
Maybe today our love can fly high
You and I will soar

Problem Description

There is a tree $T$ with $n$ nodes, where the root is $1$. Each node has a node weight $w_i$ which is $0/1$.

We define the weather value of some DFS order $s$ of this tree $T$ as:

$$\left|w_{s_1}-w_{s_2}\right|+\left|w_{s_2}-w_{s_3}\right|+\cdots+\left|w_{s_{n-1}}-w_{s_n}\right|$$

Please find the sum of the weather values over all DFS orders of the tree $T$.

:::info[DFS order] For a tree rooted at $1$, its DFS order refers to a sequence of length $n$ formed by the order in which nodes are visited (entered) when traversing the whole tree starting from the root, following the rules of depth-first search (DFS).

In a standard DFS process, the following principles are followed:

• Start from the root node. Each time a node is visited, immediately recursively visit one of its unvisited children.
• Only after all children of the current node have been visited will the traversal backtrack to its parent.
• During the whole traversal, each node is visited (recorded into the sequence) exactly once. :::

:::info[All DFS orders] In a typical DFS algorithm, when a node has multiple children, the algorithm may choose any child as the next one to visit. This freedom in choosing the visiting order of children means that the same tree may generate many different DFS orders.

“All DFS orders” means: during the traversal of this tree, enumerate all permutations of the children of each node as the visiting order, and take the set of all valid DFS traversal sequences generated in this way. :::

Output the answer modulo $998,244,353$.

Input Format

The first line contains a positive integer $n$, the number of nodes.
The second line contains $n$ integers $w_i$, the node weights.
The next $n-1$ lines each contain two positive integers $u,v$, indicating that there is an edge connecting $u$ and $v$.

Output Format

One line, the result of the answer modulo $998,244,353$.

4
0 1 0 1
1 2
1 3
3 4

4

Hint

Sample Explanation

There are two DFS orders: $[1,2,3,4],[1,3,4,2]$. They correspond to node-weight sequences $[0,1,0,1],[0,0,1,1]$, and the answer is $4$.

Constraints

Subtask ID	$n\le$	Special Property	Score
$0$	$10$	None	$15$
$1$	$10^5$	$w_1=1,w_i=0(i\neq 1)$	$10$
$2$	^	All leaves have the same weight	$30$
$3$		None	$45$

For $100\%$ of the testdata, it is guaranteed that $1\le u,v\le n\le 10^5，w_i\in\{0,1\}$。

Translated by ChatGPT 5