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