← 返回题目列表

Codeforces · 1118/F2

F2. 砍树(困难版)

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

给你一棵由 $$$n$$$ 个顶点组成的无向树。

一些顶点被着色为 $$$k$$$ 颜色之一,一些顶点没有着色。保证树至少包含 $$$k$$$ 颜色中的每一种颜色的一个顶点。可能没有未着色的顶点。

您选择 $$$k - 1$$$ 边的子集并将其从树中删除。树分解成 $$$k$$$ 连接的组件。如果结果组件都不包含不同颜色的顶点,我们称这个边子集为“nice”。

给定的树中有多少个漂亮的边子集?如果一个子集中存在某些边缘而另一个子集中不存在某些边缘,则认为两个子集是不同的。

答案可能很大,所以打印它对 $$$998244353$$$ 取模。

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le n \le 3 \cdot 10^5$$$, $$$2 \le k \le n$$$) — 分别是树中的顶点数和颜色数。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le k$$$) — 顶点的颜色。 $$$a_i = 0$$$ 表示顶点 $$$i$$$ 未着色,任何其他值表示顶点 $$$i$$$ 着色为该颜色。

接下来的 $$$n - 1$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$v_i$$$ 和 $$$u_i$$$ ($$$1 \le v_i, u_i \le n$$$, $$$v_i \ne u_i$$$) — 树的边缘。保证给定的边形成一棵树。保证树至少包含 $$$k$$$ 颜色中的每一种颜色的一个顶点。可能没有未着色的顶点。

输出

打印一个整数——给定树中边的良好子集的数量。如果一个子集中存在某些边缘而另一个子集中不存在某些边缘,则认为两个子集是不同的。

答案可能很大,所以打印它对 $$$998244353$$$ 取模。

示例

输入 #1

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

输出 #1

1

输入 #2

7 3
0 1 0 2 2 3 0
1 3
1 4
1 5
2 7
3 6
4 7

输出 #2

4

注意

这是第一个示例中的树:

唯一好的子集是边 $$$(2, 4)$$$。删除它会使树分解为组件 $$$\{4\}$$$ 和 $$$\{1, 2, 3, 5\}$$$。第一个分量仅包括颜色 $$$1$$$ 的顶点,第二分量仅包括颜色 $$$2$$$ 的顶点和未着色的顶点。

这是第二个示例中的树:

好的子集是 $$$\{(1, 3), (4, 7)\}$$$, $$$\{(1, 3), (7, 2)\}$$$, $$$\{(3, 6), (4, 7)\}$$$ 和 $$$\{(3, 6), (7, 2)\}$$$。