31153번 - Werewolves 다국어

문제

You are given a colored tree on $n$ nodes, node $i$ has color $c_i$. As a reminder, a tree on $n$ nodes is a connected graph with $n-1$ edges.

Compute the number of connected subgraphs of this tree, for which there exists some color (majority color), such that strictly more than half of the nodes of this subgraph have this color.

Since the answer can be quite large, compute it modulo 998ドル,244円,353円$.

입력

The first line of input contains one integer $n$ (1ドル \le n \le 3000$) --- the number of nodes in the tree.

The second line contains $n$ integers $c_1\ c_2\ \ldots\ c_n$ (1ドル \le c_i \le n$) --- the colors of the nodes.

The $i$-th of next $n-1$ lines contains 2ドル$ integers $u_i, v_i$ (1ドル \le u_i, v_i \le n,ドル $u_i \neq v_i$), representing the edge $(u_i, v_i)$ of the tree. It is guaranteed that the given graph is a tree.

출력

Print a single integer --- answer to the problem modulo 998ドル,244円,353円$.

제한

노트

In the following pictures, we use blue for color 1ドル,ドル red for color 2ドル,ドル and yellow for color 3ドル$. The first example looks as follows:

The tree has a total of 6ドル$ non-empty connected subgraphs: 3ドル$ of size 1ドル,ドル 2ドル$ of size 2ドル$ and 1ドル$ of size 3ドル,ドル the latter in fact being the whole tree. All such subgraphs of sizes 1ドル$ and 3ドル$ have a majority color. For those of size 2ドル$ only the subgraph induced by vertices 1ドル$ and 2ドル$ does not have a majority color (red and yellow both appear equally often in it). Therefore, there are 6ドル - 1 = 5$ connected subgraphs with a majority color.

The second example looks as follows, and it has 8ドル$ connected subgraphs with a majority color: