P17438 "LWLV Round 1" Mr. Weather

>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

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

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

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

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