#P1118F2. Tree Cutting (Hard Version)

    ID: 2801 远端评测题 2000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>combinatoricsdfs and similardptrees*2700

Tree Cutting (Hard Version)

Description

You are given an undirected tree of nn vertices.

Some vertices are colored one of the kk colors, some are uncolored. It is guaranteed that the tree contains at least one vertex of each of the kk colors. There might be no uncolored vertices.

You choose a subset of exactly k1k - 1 edges and remove it from the tree. Tree falls apart into kk connected components. Let's call this subset of edges nice if none of the resulting components contain vertices of different colors.

How many nice subsets of edges are there in the given tree? Two subsets are considered different if there is some edge that is present in one subset and absent in the other.

The answer may be large, so print it modulo 998244353998244353.

The first line contains two integers nn and kk (2n31052 \le n \le 3 \cdot 10^5, 2kn2 \le k \le n) — the number of vertices in the tree and the number of colors, respectively.

The second line contains nn integers a1,a2,,ana_1, a_2, \dots, a_n (0aik0 \le a_i \le k) — the colors of the vertices. ai=0a_i = 0 means that vertex ii is uncolored, any other value means the vertex ii is colored that color.

The ii-th of the next n1n - 1 lines contains two integers viv_i and uiu_i (1vi,uin1 \le v_i, u_i \le n, viuiv_i \ne u_i) — the edges of the tree. It is guaranteed that the given edges form a tree. It is guaranteed that the tree contains at least one vertex of each of the kk colors. There might be no uncolored vertices.

Print a single integer — the number of nice subsets of edges in the given tree. Two subsets are considered different if there is some edge that is present in one subset and absent in the other.

The answer may be large, so print it modulo 998244353998244353.

Input

The first line contains two integers nn and kk (2n31052 \le n \le 3 \cdot 10^5, 2kn2 \le k \le n) — the number of vertices in the tree and the number of colors, respectively.

The second line contains nn integers a1,a2,,ana_1, a_2, \dots, a_n (0aik0 \le a_i \le k) — the colors of the vertices. ai=0a_i = 0 means that vertex ii is uncolored, any other value means the vertex ii is colored that color.

The ii-th of the next n1n - 1 lines contains two integers viv_i and uiu_i (1vi,uin1 \le v_i, u_i \le n, viuiv_i \ne u_i) — the edges of the tree. It is guaranteed that the given edges form a tree. It is guaranteed that the tree contains at least one vertex of each of the kk colors. There might be no uncolored vertices.

Output

Print a single integer — the number of nice subsets of edges in the given tree. Two subsets are considered different if there is some edge that is present in one subset and absent in the other.

The answer may be large, so print it modulo 998244353998244353.

Samples

样例输入 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

Note

Here is the tree from the first example:

The only nice subset is edge (2,4)(2, 4). Removing it makes the tree fall apart into components {4}\{4\} and {1,2,3,5}\{1, 2, 3, 5\}. The first component only includes a vertex of color 11 and the second component includes only vertices of color 22 and uncolored vertices.

Here is the tree from the second example:

The nice subsets are {(1,3),(4,7)}\{(1, 3), (4, 7)\}, {(1,3),(7,2)}\{(1, 3), (7, 2)\}, {(3,6),(4,7)}\{(3, 6), (4, 7)\} and {(3,6),(7,2)}\{(3, 6), (7, 2)\}.