UOJ Logo Universal Online Judge

UOJ

#929. 【清华集训2024】颠倒歌

附件下载 统计

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

对于两棵树 T1(V1,E1),T2(V2,E2),若 V1=V2,我们称 T1T2 当且仅当对于任意 S2V2,存在 S1 满足 S2S1V1f(S1,T1)f(S2,T2)

T1,T2 等价当 T1T2T2T1,记作 T1T2。该等价关系将 n 个点的有标号树划分成若干等价类。

问:

  1. 给定 kn 个点的树 T1,T2,Tk,求满足 TTi,1ik有标号树 T 构成的等价类数量。

  2. 给定 kn 个点的树 T1,T2,Tk,求满足 TiT,1ik有标号树 T 数量。

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

保证答案取模后非 0

输入格式

从标准输入读入数据。

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

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

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

输出格式

输出到标准输出。

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

样例 #1

样例输入 #1

0
1 4
1 2
1 3
1 4

样例输出 #1

2

【样例 1 解释】

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

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

样例 #2

样例输入 #2

1
1 4
1 2
2 3
3 4

样例输出 #2

16

【样例 2 解释】

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

【样例 3 ~ 10】

见题目目录下的 3.in ~ 10.in3.ans ~ 10.ans

子任务

对于所有数据,保证 p{0,1}3n50001k10001u,vn,答案取模后不等于 0

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

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