3096. [HSOI 2019] HS的颓废生活

【题目背景】

HS又弱又颓，HAOI2019 HS退役稳了呀【真香】！蒟蒻HS像往常一样悄悄的打开COGS胡点了一拨随机题目。。。咦，树上的点对，这题太水了吧，不行我要弄个加强版。。。于是HS便开始了他的颓废生活。。。

【题目描述】

给一棵有n个节点的树，每条边长度都为1。定义dist(u,v)=节点u到节点v的最短路距离。给出一个整数k，写一个程序，对于给定的树，计算有多少对顶点对（（1，2）和（2，1）算一对）长度为i（0<=i<=k）,由于对数过多，请将每个答案余除998244353

【输入格式】

第一行,两个整数n,k

第二到第n行，每行有两个数u,v 表示u到v有一条无向边

【输出格式】

一行k+1个数，表示i=0,1...k时的答案

【样例输入】

7 5
1 2 
1 3
1 4
2 5
2 6
3 7

【样例输出】

7 6 7 6 2 0

【提示】

30%数据满足n,k<=1000

50%数据满足n,k<=10000

100%数据满足n,k<=100000

为了防止某些大佬暴力水过，HS将数据规模加大，时限改为2s,可能会有一些卡常

正解时间复杂度太玄学了，但此题较为经典，祝大家水题愉快！

【来源】

HS