题目描述

给你一棵包含 $n$ 个节点的树。

树上每个节点要么被染成蓝色，要么被染成红色，要么没有染色。数据保证至少有一个节点被染成蓝色，同时至少有一个节点被染成红色。

你现在要删掉树上的恰好一条边（删掉一条边之后树变成两个连通块），使得：

• 其中一个连通块仅包含蓝色或未染色的结点；
• 另一个连通块仅包含红色或未染色的结点。

即：两个连通块中不存在任何一个连通块既存在蓝色节点又存在红色节点的情况出现。

问：有几条边是满足条件的？

输入格式

第一行，一个整数 $n(2 \le n \le 2 \cdot 10^5)$。

第二行，$n$ 个整数 $a_1, a_2, \ldots, a_n(0 \le a_i \le 2)$。其中 $a_i = 1$ 表示节点 $i$ 被染成了红色，$a_i = 2$ 表示节点 $i$ 被染成了蓝色，$a_i = 0$ 表示节点 $i$ 没有被染色。

接下来 $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

说明/提示

样例解释

样例1：

只能删掉连接节点 $(2, 4)$ 的边。

样例2：

每条边都可以删。

样例3：

没有一条边满足条件。

数据规模与约定

• 对于 $20\%$ 的数据，$n \le 20$
• 对于 $50\%$ 的数据，$n \le 2000$
• 对于 $100\%$ 的数据，$2 \le n \le 2 \cdot 10^5$