You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

你有一棵 $n$ 个点的无根树，节点的编号为 $1, 2, \ldots, n$。定义树上两点之间的距离 $\operatorname{dis}(i, j)$ 为树上 $i$ 点到 $j$ 点的简单路径上的边数。

现在有 $k$ 个关键点 $a_1, a_2, \ldots, a_k$，对于每个点，我们想求出距离它最近的关键点是哪个点。也就是对于一个点 $v$，令 $f(v)$ 表示令 $\operatorname{dis}(v, a_i)$ 最小的 $i$，如果有多个 $i$ 满足条件，那么我们会选择其中最小的 $i$。

现在，我们给出了 $f(1), f(2), \ldots, f(n)$，问有多少组可能的 $(a_1, a_2, \ldots, a_k)$ 满足条件。由于答案可能很大，输出对 $998244353$ 取模的结果。

输入格式

多组测试数据，第一行一个整数 $T$ 表示数据组数。
对于每组测试数据，第一行两个整数 $n, k$，表示节点个数和关键点个数。
接下来 $n - 1$ 行，每行两个整数 $u, v$，表示一条树边 $(u, v)$。
接下来一行，$n$ 个整数，$f(1), f(2), \ldots, f(n)$。注意：数据不保证一定存在一组可能的 $(a_1, a_2, \ldots, a_k)$。

输出格式

对于每组数据，输出一个整数，表示答案对 $998244353$ 取模的结果。

3
3 3
1 2
2 3
1 2 1
3 2
1 2
2 3
1 2 2
3 2
1 2
2 3
2 1 1

0
1
2

1
10 5
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
1 1 2 2 3 3 4 4 5 5

13

提示

【样例 #1 解释】

在第一个样例中，对于第二组数据，一个解为 $(1, 2)$。对于第三组数据，两个解为 $(2, 1), (3, 1)$。

注意，当多个点距离相同时，我们选择的是最小的 $i$ 而不是 $a_i$。

【样例 #3】

见附件中 voronoi/voronoi3.in 与 voronoi/voronoi3.ans，这个样例满足测试点 $3 \sim 4$ 的条件限制。

【样例 #4】

见附件中 voronoi/voronoi3.in 与 voronoi/voronoi3.ans，这个样例满足测试点 $7 \sim 10$ 的条件限制。

【数据范围】

对于所有的数据，保证 $1 \le T \le 10$，$2 \le k \le n \le 3 \times {10}^3$，$1 \le f(i) \le k$。

具体如下：

特殊性质 A：保证树是一条链。
特殊性质 B：保证 $k = 2$。