#H1082. H. ‘Yorida Yoshino’ MSF_Akatsuki 和他的最后灰姑娘计划

H. ‘Yorida Yoshino’ MSF_Akatsuki 和他的最后灰姑娘计划

题目背景

近日,里泰尔德弹幕网上 Vocal 区新人热门 No. 1 引起了众多群友注意。这位 V 圈[1]新宠儿最近的几次投稿都引发了跨圈级别的关注,同时屡次冲上首页推荐和原创曲周刊——没错,她不仅没有用“耗时 998244353 小时爆肝”等传统美德标题,也没有在评论区和动态热情营业,还是一人词曲编混 PV(且均达到业余级[2]的亮眼水平)的超强原创一体机。加上 151cm 的身高、40kg 的体重(万能的群友人工测量得出),还有理所当然的甜美声线,她的粉丝和再生数实现了指数级增长。

依田芳乃这个并不起眼的名字,短短几天内就在群里被 cue 了若干次。据传(群友截图动态)她已经打算发起众筹,在里泰尔德剧院开展一次线下演唱会。让我们继续等待前方群友发回的最新消息。

题目描述

M晓在 OIER 之中总是最为冷静和成熟(可能是人设需求),尽管似乎并没有获得任何力量,他依旧凭借自己的努力成为了里泰尔德互联网圈的一颗闪耀新星。

他的最后灰姑娘计划也依托他的偶像身份而生。他的粉丝群体构成了一个 nn 个结点,n1n-1 条边的无向连通图,或者也可以将其称之为树。M晓打算重构这棵树,他对它进行了如下操作:

首先对完整的树找到一个结点,这个结点满足它的最大子树是所有结点的最大子树组成的集合中最小的。他把这个结点叫做这棵树的爱丽丝结点,如果有多个,他会看心情任选一个;

然后,将这个爱丽丝结点作为根,对它的所有子树分别找到它们的爱丽丝结点,然后将这些结点与完整的树的爱丽丝结点用画笔连接,每条连接的边的长度均为 11

持续不断地执行这个过程,直到所有结点都成为某棵树的爱丽丝结点之后,将画笔连起来的新树叫做爱丽丝树。爱丽丝树将最重要的结点连接起来,信息产生的叙事能量全部输入给他计划中的“灰姑娘”。

然而,仅仅是一棵树的力量是不够的。经过他这段时间与莉莉安娜的策划,发现爱丽丝树的逆向还原是千变万化的,并且每一棵原树都能为他们所用。

现在他们已经构建出了一棵爱丽丝树,我们称这棵树为 TT。对于任意的一棵树,因为爱丽丝结点的选择不同,它可能能重构出很多爱丽丝树;但只要它能重构出 TT,M晓就能够攫取它的能量。每一棵树的简单路径都拥有着叙事能量,且不同长度的简单路径叙事能量不同。因此,M晓想要知道对于所有能重构出 TT 的原树,它们不同长度的简单路径的数量分别求和的结果。形式化地,设能经过上述过程重构出 TT 的树集合为 SS,树 TT' 的所有简单路径集合为UTU_{T'},求对于任意 iZ+[1,n]i\in\mathbb Z^+\cap[1,n]ansians_i 的值,其中

ansi=TSPUT[len(P)=i]ans_i=\sum_{\forall T'\in S}\sum_{P\in U_{T'}}[len(P)=i]

len(P)len(P) 表示路径的长度,方括号为 Iverson bracket,即方括号内的条件为真则其值为 11,否则为 00

而你,作为被选中的“辛德瑞拉”,也想知道你究竟能够获得多少力量。

数据格式与约定

输入

输入第一行包含两个整数 n(1n5×103)n(1 \le n \le 5\times10^3)rt(1rtn)rt(1 \le rt \le n),表示结点个数和爱丽丝树的根结点。

接下来 n1n-1 行,每行两个整数 xxyy,表示在爱丽丝树上,编号为 xx 的结点和编号为 yy 的结点被画笔连接。

输出

输出包含一行 n1n-1 个整数 ansians_i,表示长度为ii的路径数量对 998244353998244353 取模的结果。

样例

2 2
1 2
1
5 1
1 4
1 3
1 5
5 2
8 8 4 0
11 1
1 2
2 3
2 5
2 6
3 4
1 7
7 8
8 9
7 10
10 11
2000 2240 2000 1592 1296 976 576 256 64 0

后记

里泰尔德剧院的大舞台上。

充满奇异色彩和高拟真特效的灯与其他效果打在舞台中央。M晓站在聚光中,静静地感受着这 56 年前根本无法做到的舞美。

他睁开双眼。那是一双已经不再拥有神采的眸子,但此刻,它们正闪着光。

“谢谢大家今天来听我的演出。”

沉默之后,是掌声与欢呼声。


  1. 是的,在 2077 年,V 圈既不是术力口圈也不是 VTB 圈,而是 Vocal 圈。 ↩︎

  2. 所谓业余级,即一般通过路人眼中的神仙。 ↩︎