Connected Subtrees with Limited Team Diversity

You are given a tree with n vertices (cities) numbered from 1 to n and n-1 bidirectional edges connecting them such that any two cities are reachable from each other. Each city i supports a team given by an integer a_i.

Your task is to choose a set of cities in which to build football stadiums such that:

1. The chosen set of cities (which is nonempty) induces a connected subgraph. In other words, for any two cities with a stadium there exists a path between them that uses only cities where stadiums are built.
2. Among the chosen cities, there do not exist three cities supporting three pairwise different teams. Equivalently, the set of teams among the chosen cities contains at most two distinct numbers.

You need to count the number of different ways to choose such a set of cities. Two ways are considered different if there exists at least one city which is built in one scheme and not built in the other. Finally, output the answer modulo 998244353 (i.e. the remainder when the answer is divided by 998244353).

Note on the team diversity constraint: For any connected subset of chosen cities, if there are three or more distinct team numbers then one can always pick three cities with pairwise different team numbers. Hence the allowed connected subtrees have team count equal to 1 or 2.

inputFormat

The input is given as follows:

n
a1 a2 ... an
u1 v1
u2 v2
... 
un-1 vn-1

Here, the first line contains an integer n (the number of cities). The second line contains n integers, where the i-th integer represents a_i, the team supported by city i. Each of the following n-1 lines contains two integers u and v indicating that there is a bidirectional road between cities u and v.

outputFormat

Output a single integer: the number of valid ways to choose a set of cities to build stadiums, taken modulo 998244353.

sample

3
1 1 2
1 2
2 3

6