P11424 [清华集训 2024] 颠倒歌

对于树 $T(V, E)$ 和 $S ⊆ 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 ≼ T_2$ 当且仅当对于任意 $S_2 ⊆ V_2$，存在 $S_1$ 满足 $S_2 ⊆ S_1 ⊆ V_1$ 且 $f(S_1, T_1) ≤ f(S_2, T_2)$。 称 $T_1, T_2$ 等价当 $T_1 ≼ T_2$ 且 $T_2 ≼ T_1$，记作 $T_1 ∼ T_2$。该等价关系将 $n$ 个点的有标号树划分成若干等价类。 问： 1. 给定 $k$ 棵 $n$ 个点的树 $T_1, T_2 \dots , T_k$，求满足 $T ≼ T_i, ∀1 ≤ i ≤ k$ 的**有标号树 $T$ 构成的等价类**数量。 2. 给定 $k$ 棵 $n$ 个点的树 $T_1, T_2 \dots , T_k$，求满足 $T_i ≼ T, ∀1 ≤ i ≤ k$ 的**有标号树** $T$ 数量。 注意两问的计数对象不同。两问答案均对 $998, 244, 353$ 取模。 保证答案取模后非 $0$。

从标准输入读入数据。 输入第一行一个整数 $p$，其中 $p ∈ \{0, 1\}$，$p = 0$ 表示询问第一问，否则表示询问第二问。 接下来一行两个正整数 $k, n$，分别表示输入树的数量以及点数。 接下来依次输入 $k$ 棵树，对于每棵树输入 $n - 1$ 行每行两个正整数 $u, v$ 描述树中的一条边。

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

### 【样例 1 解释】 可以证明 $4$ 个点的有标号树被划分成了 $5$ 个等价类，所有的链在同一个等价类，而其它分别以每个点为菊花中心对应一个等价类。 可以验证链对应的等价类和该树本身所在的等价类均满足要求，而其他等价类不满足要求。 ### 【样例 2 解释】 可以验证所有 $4$ 个点的有标号树共 $16$ 个均满足要求。 ### 【样例 3 ~ 10】 见题目目录下的 `3.in` ~ `10.in` 与 `3.ans` ~ `10.ans`。 ### 【子任务】 对于所有数据，保证 $p ∈ \{0, 1\}$，$3 ≤ n ≤ 5000$，$1 ≤ k ≤ 1000$，$1 ≤ u, v ≤ n$，答案取模后不等于 $0$。 | 子任务编号 | $p$ | $n$ | $k$ | 树形态 | 分数 | | :-: | :-: | :-: | :-: | :-: | :-: | | $1$ | $\in\{0,1\}$ | $\le8$ | $\le4$ | 无特殊形态 | $10$ | | $2$ | $=0$ | $\le200$ | $\le1$ | 菊花 | $4$ | | $3$ | $=0$ | $\le200$ | $\le1$ | 无特殊形态 | $8$ | | $4$ | $=0$ | $\le200$ | $\le2$ | 无特殊形态 | $9$ | | $5$ | $=0$ | $\le200$ | $\le40$ | 无特殊形态 | $10$ | | $6$ | $=0$ | $\le5000$ | $\le10^3$ | 无特殊形态 | $14$ | | $7$ | $=1$ | $\le200$ | $\le1$ | 链 | $7$ | | $8$ | $=1$ | $\le200$ | $\le1$ | 无特殊形态 | $7$ | | $9$ | $=1$ | $\le200$ | $\le2$ | 无特殊形态 | $10$ | | $10$ | $=1$ | $\le200$ | $\le40$ | 无特殊形态 | $10$ | | $11$ | $=1$ | $\le5000$ | $\le10^3$ | 无特殊形态 | $11$ | “树形态”中，“菊花”指存在一个向所有点有直接连边的点，“链”指所有点度数不超过 $2$。