题目描述

有 $n$ 间屋子，由 $n-1$ 条双向道路连接成了一个树形结构。其中，第 $i$ 间屋子里居住了 $1 $ 个种族为 $c_i$ 的狼人。

现在你要召集一个连通块内的狼人。设 $a_j$ 表示被召集的种族为 $j$ 的狼人个数，若存在 $2a_k>\sum a_j$， 则种族为 $k$ 的狼人会造反。

你想知道有多少个连通块会使某种狼人造反，答案对 $998244353$ 取模。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $c_i$。

接下来 $n-1$ 行，每行两个整数 $u,v$，表示有一条边连接第 $u$ 间和第 $v$ 间屋子。

输出格式

一行一个整数，表示答案。

样例

3
2 3 3
1 2
2 3

5

4
1 1 3 3
1 2
1 3
1 4

8

15
5 13 5 1 13 5 14 6 14 12 8 1 12 14 5
2 1
7 1
8 4
10 3
15 1
1 9
1 6
13 1
5 2
14 15
3 9
1 4
3 12
10 11

104

数据范围 对于 $30\%$ 的数据， $n\le 20$。 对于另外 $20\%$ 的数据，树为 $1->n$ 的链。 对于另外 $20\%$ 的数据， $c_i\le 2$。 对于 $100\%$ 的数据， $n\le 3000,c_i\le n$。