给你一棵由 $$$n$$$ 个顶点组成的无向树。
有些顶点是蓝色的,有些是红色的,有些是无色的。保证树包含至少一个红色顶点和至少一个蓝色顶点。
您选择一条边并将其从树中删除。树分成两个相连的部分。如果生成的组件都不包含红色和蓝色的顶点,我们称一条边为“nice”。
给定的树中有多少条漂亮的边?
输入
第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$) — 树中的顶点数。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 2$$$) — 顶点的颜色。 $$$a_i = 1$$$ 表示顶点 $$$i$$$ 为红色,$$$a_i = 2$$$ 表示顶点 $$$i$$$ 为蓝色,$$$a_i = 0$$$ 表示顶点 $$$i$$$ 为无色。
接下来的 $$$n - 1$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$v_i$$$ 和 $$$u_i$$$ ($$$1 \le v_i, u_i \le n$$$, $$$v_i \ne u_i$$$) — 树的边缘。保证给定的边形成一棵树。保证树包含至少一个红色顶点和至少一个蓝色顶点。
输出
打印一个整数——给定树中的好边数。
示例
输入 #1
5 2 0 0 1 2 1 2 2 3 2 4 2 5
输出 #1
1
输入 #2
5 1 0 0 0 2 1 2 2 3 3 4 4 5
输出 #2
4
输入 #3
3 1 1 2 2 3 1 3
输出 #3
0
注意
这是第一个示例中的树:
唯一好的边是边 $$$(2, 4)$$$。删除它会使树分解为组件 $$$\{4\}$$$ 和 $$$\{1, 2, 3, 5\}$$$。第一分量仅包括红色顶点,第二分量包括蓝色顶点和无色顶点。
这是第二个示例中的树:
每个边缘都很好。
这是第三个示例中的树:
边 $$$(1, 3)$$$ 将其分割为 $$$\{1\}$$$ 和 $$$\{3, 2\}$$$ 两个部分,后者同时包含红色和蓝色顶点,因此边缘不好。边 $$$(2, 3)$$$ 将其分成 $$$\{1, 3\}$$$ 和 $$$\{2\}$$$ 两个部分,前一个同时包含红色和蓝色顶点,因此边缘也不好。所以答案是0。