8597: Everlasting Transeunt

Falcom is a historical company whose work "Ys VIII -Lacrimosa of DANA-" is highly acclaimed.

Remoon wants to get the platinum trophy of this game for all versions, and he notices that the game has n versions, indexed from $1$ to $n$. A quick way to achieve this is to copy data between different versions. Unfortunately, due to compatibility issues, data in each version cannot be loaded in other versions. Nevertheless, remoon gets n−1 editors, where the $i$-th editor can rewrite data in version u_i, such that the rewritten data can be loaded in version v_i. It is also possible to use the $i$-th editor to change data in version v_i to data in version u_i. It is guaranteed that any two versions can transform into each other through the $n-1$ editors.

To distinguish between each version, remoon gives each version j a magic integer a_j. If for any editor, a_ui≠a_vi. Then remoon can distinguish whether the editor has correctly rewritten a version or not. Besides, to limit the magic number's size, remoon gives an upper bound integer sequence b₁,...,b_n and require that for i∈{1,2,...,n}, we have 1≤a_i≤b_i.

Remoon wonders how many ways to choose a₁,...,a_n so that he can correctly distinguish between the versions. Two ways a₁,...,a_n and a₁′,...,a_n′ are considered different if and only if there exists 1≤i≤n such that a_i≠a_i′. As the answer may be too large, you only need to output the answer modulo 998244353.

The first line contains an integer n(1≤n≤5×10⁵), denoting the number of versions.

The second line contains n integers b₁,b₂,…,b_n(1≤b_i<998244353), denoting the upper bound on the magic integer on each version.
Then n−1 lines follow, where the j(1≤j≤n−1)-th line contains two integers u_j and v_j, denoting the j-th editor can copy data between version u_j and v_j.

Output an integer in a line, denoting the answer taken modulo 998244353.

5
1 2 3 4 5
1 2
2 3
3 4
4 5

24