题目描述

给定一棵大小为 $n$ 的树，节点编号从 $1$ 到 $n$。

我们用 $c_i$ 表示节点 $i$ 的颜色，有如下三种情况：

• $c_i = 1$：表示节点 $i$ 是红色的；
• $c_i = 2$：表示节点 $i$ 是蓝色的；
• $c_i = 0$：表示节点 $i$ 是无色的。

红色和蓝色的节点是染色的节点；无色的节点是没有染色的节点。

现在你要选择树上的一条边删除，很明显，删除这条边之后，这棵树会变成两棵子树。

你需要让每棵子树中所有染色的节点都是同一种颜色。

问：有多少条边满足要求？

即，你需要回答出：这棵树中存在多少条边，使得当你删除这条边之后，剩下的两棵子树满足下述条件：

• 其中一棵子树中所有染色的节点（如果存在的话）都是红色，或者都是蓝色；
• 并且另一棵子树中所有染色的节点（如果存在的话）都是红色，或者都是蓝色。

输入格式

第一行，一个整数 $n(2 \le n \le 3 \cdot 10^5)$，表示树的大小（即这棵树包含多少个节点）。

第二行，$n$ 个整数 $c_1, c_2, \ldots, c_n(0 \le c_i \le 2)$，表示每个节点的颜色。

接下来 $n-1$ 行，每行包含两个整数 $u_i$ 和 $v_i$，表示树上一条边连接的两个节点的编号（$1 \le u_i,v_i \le n, u_i \neq v_i$）。

输出格式

输出一个整数，表示树上存在多少条边满足题目要求。

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

1

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

4

3
1 1 2
2 3
1 3

0

说明/提示

样例解释

以下均用 $(u, v)$ 表示连接节点 $u$ 和 $v$ 的那条边。

样例1，如图：

满足条件的只有边：$(2,4)$.

样例2，如图：

所有边都满足条件.

样例1，如图：

没有边满足条件.

数据规模与约定

• 对于 $30\%$ 的数据，$n \le 30$

• 对于 $60\%$ 的数据，$n \le 3000$

• 对于 $100\%$ 的数据，$2 \le n \le 3 \cdot 10^5, 0 \le c_i \le 2$