#PQJ36x2304. QOJ 36_2304
QOJ 36_2304
1 线图 1.1 题目描述 九条可怜是一个热爱出题的女孩子。 今天可怜想要出一道和图论相关的题。在一张无向图G 上,我们可以对它进行一些非常有 趣的变换,比如说对偶,又或者说取补。这样的操作往往可以赋予一些传统的问题新的活力。例 如求补图的连通性、补图的最短路等等,都是非常有趣的问题。 最近可怜知道了一种新的变换:求原图的线图(line graph)。对于无向图G = ⟨V, E⟩,它的 线图L(G) 也是一个无向图: • 它的点集大小为|E|,每个点唯一对应着原图的一条边。 • 两个点之间有边当且仅当这两个点对应的边在原图上有公共点(注意不会有自环)。 下图是一个简单的例子,左图是原图,右图是它对应的线图。其中点1 对应原图的边(1, 2), 点2 对应(1, 4),点3 对应(1, 3),点4 对应(3, 4)。 经过一些初步的摸索,可怜发现线图的性质要比补图复杂很多,其中突出的一点就是补图 的补图会变回原图,而L(L(G)) 在绝大部分情况下不等于G,甚至在大多数情况下它的点数和 边数会以很快的速度增长。 因此,可怜想要从最简单的入手,即计算Lk(G) 的点数(Lk(G) 表示对G 求k 次线图)。 然而遗憾的是,即使是这个问题,对可怜来说还是太困难了,因此她进行了一定的弱化。她 给出了一棵n 个节点的树T,现在她想让你计算一下Lk(T) 的点数。 1.2 输入Ḑᓣ 第一行输入两个整数n, k,表示树的点数以及连续求线图的次数。 接下来n −1 行每行两个整数u, v 表示树上的一条边。 1.3 输出Ḑᓣ 输出一行一个整数,表示答案对998244353 取模后的值。 2
1.4 样例输入 5 3 1 2 2 3 2 5 3 4 1.5 样例输出 5 1.6 样例解䞞 如下图所示,左图为原树,中图为L(G),右图为L2(G)。这儿并未画出L3(G),但是由于 L2(G) 有5 条边,因此L3(G) 中有5 个点。 1.7 数据㣗ೈ与约定 测试点 k 测试点 k 1 = 2 6 = 6 2 = 3 7 = 7 3 = 4 8 = 8 4 = 5 9 = 9 5 10 对于100% 的数据,2 ≤n ≤5000。 3