A6739. 「SNOI2024」树 V 图
编程题
提高+/省选-
知识点
题目描述
你有一棵 $n$ 个点的无根树，节点的编号为 $1, 2, \dots, n$。定义树上两点之间的距离 $\text{dis} (i, j)$ 为树上 $i$ 点到 $j$ 点的简单路径上的边数。
现在有 $k$ 个关键点 $a_1, a_2, \dots, a_k$，对于每个点，我们想求出距离它最近的关键点是哪个点。也就是对于一个点 $v$，令 $f(v)$ 表示令 $\text{dis}(v, a_i) $ 最小的 $i$，如果有多个 $i$ 满足条件，那么我们会选择其中最小的 $i$。
现在，我们给出了 $f(1), f(2), \dots, f(n)$，问有多少组可能的 $(a_1, a_2, \dots, a_k)$ 满足条件。由于答案可能很大，输出对 $998244353$ 取模的结果。
现在有 $k$ 个关键点 $a_1, a_2, \dots, a_k$，对于每个点，我们想求出距离它最近的关键点是哪个点。也就是对于一个点 $v$，令 $f(v)$ 表示令 $\text{dis}(v, a_i) $ 最小的 $i$，如果有多个 $i$ 满足条件，那么我们会选择其中最小的 $i$。
现在，我们给出了 $f(1), f(2), \dots, f(n)$，问有多少组可能的 $(a_1, a_2, \dots, a_k)$ 满足条件。由于答案可能很大，输出对 $998244353$ 取模的结果。
输入格式
多组测试数据，第一行一个整数 $T$ 表示数据组数。
对于每组测试数据，第一行两个整数 $n, k$，表示节点个数和关键点个数。
接下来 $n-1$ 行，每行两个整数 $u, v$，表示一条树边 $(u, v)$。
接下来一行，$n$ 个整数，$f(1), f(2), \dots, f(n)$。注意：数据 **不保证** 一定存在一组可能的 $(a_1, a_2, \dots, a_k)$。
对于每组测试数据，第一行两个整数 $n, k$，表示节点个数和关键点个数。
接下来 $n-1$ 行，每行两个整数 $u, v$，表示一条树边 $(u, v)$。
接下来一行，$n$ 个整数，$f(1), f(2), \dots, f(n)$。注意：数据 **不保证** 一定存在一组可能的 $(a_1, a_2, \dots, a_k)$。
输出格式
对于每组数据，输出一个整数，表示答案对 $998244353$ 取模的结果。
输入输出样例
输入 #1
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
输出 #1
0 1 2
输入 #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
输出 #2
13
说明/提示
对于所有的数据，保证 $1\leq T \leq 10$，$2 \leq k\leq n \leq 3\times 10^3$，$ 1\leq f(i) \leq k$。
具体如下：
| 测试点编号 | $n\leq$ | 特殊性质 |
|:----------:|:------:|:---:|
| $1\sim 2$ | $15$ | |
| $3\sim 4$ | $3000$ | A |
| $5\sim 6$ | $3000$ | B |
| $7\sim 10$ | $3000$ | |
特殊性质 A：保证树是一条链。
特殊性质 B：保证 $k = 2$。
具体如下：
| 测试点编号 | $n\leq$ | 特殊性质 |
|:----------:|:------:|:---:|
| $1\sim 2$ | $15$ | |
| $3\sim 4$ | $3000$ | A |
| $5\sim 6$ | $3000$ | B |
| $7\sim 10$ | $3000$ | |
特殊性质 A：保证树是一条链。
特殊性质 B：保证 $k = 2$。