AdditionalFile5332.zip

#5332. 「清华集训 2024」颠倒歌

标签: 传统 | 时间限制: 3000 ms | 内存限制: 512 MiB |

题目描述

对于树 $T(V, E)$ 和 $S \subseteq V$，记 $f(S, T)$ 表示 $T$ 的对 $S$ 的导出子图（即仅保留 $S$ 中的点和两端都在 $S$ 中的边得到的图）中度数小于等于 $1$ 的点的数量。

对于两棵树 $T_1(V_1, E_1), T_2(V_2, E_2)$，若 $V_1 = V_2$，我们称 $T_1 \preccurlyeq T_2$ 当且仅当对于任意 $S_2 \subseteq V_2$，存在 $S_1$ 满足 $S_2 \subseteq S_1 \subseteq V_1$ 且 $f(S_1, T_1) \le f(S_2, T_2)$。

称 $T_1, T_2$ 等价当 $T_1 \preccurlyeq T_2$ 且 $T_2 \preccurlyeq T_1$，记作 $T_1 \sim T_2$。该等价关系将 $n$ 个点的有标号树划分成若干等价类。

问：

1. 给定 $k$ 棵 $n$ 个点的树 $T_1, T_2 \dots , T_k$，求满足 $T \preccurlyeq T_i, \forall 1 \le i \le k$ 的有标号树 $T$ 构成的等价类数量。
2. 给定 $k$ 棵 $n$ 个点的树 $T_1, T_2 \dots , T_k$，求满足 $T_i \preccurlyeq T, \forall 1 \le i \le k$ 的有标号树 $T$ 数量。

注意两问的计数对象不同。两问答案均对 $998, 244, 353$ 取模。

保证答案取模后非 $0$。

输入格式

从标准输入读入数据。

输入第一行一个整数 $p$，其中 $p \in \{0, 1\}$，$p = 0$ 表示询问第一问，否则表示询问第二问。

接下来一行两个正整数 $k, n$，分别表示输入树的数量以及点数。

接下来依次输入 $k$ 棵树，对于每棵树输入 $n - 1$ 行每行两个正整数 $u, v$ 描述树中的一条边。

输出格式

输出到标准输出。

输出一行一个整数表示答案对 $998, 244, 353$ 取模后的结果。

样例 1

输入

0
1 4
1 2
1 3
1 4

输出

2

可以证明 $4$ 个点的有标号树被划分成了 $5$ 个等价类，所有的链在同一个等价类，而其它分别以每个点为菊花中心对应一个等价类。

可以验证链对应的等价类和该树本身所在的等价类均满足要求，而其他等价类不满足要求。

样例 2

输入

1
1 4
1 2
2 3
3 4

输出

16

可以验证所有 $4$ 个点的有标号树共 $16$ 个均满足要求。

样例 3

见题目目录下的 3.in 与 3.ans。

样例 4

见题目目录下的 4.in 与 4.ans。

样例 5

见题目目录下的 5.in 与 5.ans。

样例 6

见题目目录下的 6.in 与 6.ans。

样例 7

见题目目录下的 7.in 与 7.ans。

样例 8

见题目目录下的 8.in 与 8.ans。

样例 9

见题目目录下的 9.in 与 9.ans。

样例 10

见题目目录下的 10.in 与 10.ans。

子任务

对于所有数据，保证 $p \in \{0, 1\}$，$3 \le n \le 5000$，$1 \le k \le 1000$，$1 \le u, v \le n$，答案取模后不等于 $0$。

子任务编号	$p$	$n$	$k$	树形态	分数
$1$	$\in\{0,1\}$	$\le 8$	$\le 4$	无特殊形态	$10$
$2$	$=0$	$\le 200$	$\le 1$	菊花	$4$
$3$				无特殊形态	$8$
$4$			$\le 2$		$9$
$5$			$\le 40$		$10$
$6$		$\le 5,000$	$\le 10^3$		$14$
$7$	$=1$	$\le 200$	$\le 1$	链	$7$
$8$				无特殊形态	$7$
$9$			$\le 2$		$10$
$10$			$\le 40$		$10$
$11$		$\le 5,000$	$\le 10^3$		$11$

“树形态”中，“菊花”指存在一个向所有点有直接连边的点，“链”指所有点度数不超过 $2$。