狼人

题目描述

有的$n$间屋子被$n-1$条双向路径连通，构成树。其中第$i$个屋子中住着一个种族$c_i$的狼人。

树的一个连通子图中，若其中一个种族的狼人超过了其他种族的总和，它们可以在该连通子图中进行支配。具体而言，记$a_i$为种族为$i$的狼人在连通子图中的个数总和，则支配的条件是存在$k$使得$a_k>\sum_{i\ne k} a_i$。

那么，有多少个不同的连通子图会出现支配的情况？答案对$998244353$取模。

$\dagger$ 连通子图指点集和边集分别为原图点集和边集的子集，且连通的图。子图不同，当且仅当选择的点集和边集至少有一个不完全相同。

输入格式

第一行，一个正整数 $n$；

第二行，$n$个正整数 $c_1,c_2,\cdots,c_n$；

之后$n-1$行，每行两个正整数$u,v$，表示一条路径连接第$u,v$个屋子。

输出格式

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

样例 1

3
2 3 3
1 2
2 3

5

样例 2

见下发文件：werewolf2.in 与 werewolf2.out。

样例 3

见下发文件：werewolf3.in 与 werewolf3.out。

样例解释

样例一：唯一不合法的连通子图为点$\{1,2\}$构成的。

样例二：所有单点连通子图合法，除此之外合法的为作$\{1,2\},\{1,2,3\},\{1,2,4\},\{1,3,4\}$。

数据说明

共20个测试点分配在子任务，每个测试点5分。

下发大样例ex_B1到ex_B4依次符合如下4个子任务的要求。

对于所有数据$1 \leq n \leq 3000,1\le c_i\le n$。

更多样例

以下 4 组大样例取自原题附件：

• ex_B1.in / ex_B1.out
• ex_B2.in / ex_B2.out
• ex_B3.in / ex_B3.out
• ex_B4.in / ex_B4.out