← 返回题目列表

Codeforces · 1118/F1

F1. 砍树(简单版)

中文机器翻译题面 查看原题

给你一棵由 $$$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。