QOJ.ac

QOJ

Time Limit: 6 s Memory Limit: 1024 MB Total points: 100

# 7772. 意念力

统计

我曾经也像你一样果冻hyper,直到我的膝盖中了一箭。

我觉得我还是用果冻跳来防止速度损失过快比较好。

如果我真打算离开这里做些别的事情而不是在这里写些杂七杂八的东西,那么刚提到的东西可能会很有用。

题目描述

给定一棵$ n $个点的边带权的树和一个可行距离值$ k $,称一个集合$ S $是"合法的",当且仅当$ S $中任意两个不同元素在树上的距离都大于等于$ k $。

对于$ m=1,2,3,....,n $,求将这棵树的点集划分为无序的$ m $个非空集合,即点集中每个点恰好被$ m $个集合中的一个包含,且每个集合都是"合法的"的方案数,对$ 998244353 $取模。

输入格式

第一行两个正整数$ n,k $,表示树的点数和可行距离值。

第二行到第$ n $行,每行三个整数$ x,y,z $,表示树上一条边的两个端点,和这条边的边权。

输出格式

一行$ n $个整数,分别表示$ m=1,2,3,....,n $的答案。

输入样例1

5 2
1 2 1
1 3 1
2 4 1
2 5 1

输出样例1

0 1 7 6 1

样例输入2

10 3
1 2 1
1 3 1
2 4 1
2 5 1
3 6 1
3 7 1
4 8 1
4 9 1
5 10 1

样例输出2

0 0 0 16 308 836 674 206 25 1

数据范围

$ 2 \leq n \leq 100000,1 \leq k \leq 10^{14},1 \leq x,y \leq n,1 \leq z \leq 10^9 $。

  • Subtask 1(10 pts):$ n\leq 10 $
  • Subtask 2(15 pts):$ n\leq 2000 $,且所有边的边权均为1。
  • Subtask 3(15 pts):$ n\leq 2000 $
  • Subtask 4(15 pts):对于$ 1 \leq i \leq n-1 $,第$ i $条边满足$ x=i $,$ y=i+1 $,且所有边的边权均为$ 1 $。
  • Subtask 5(15 pts):对于$ 1 \leq i \leq n-1 $,第$ i $条边满足$ x=i $,$ y=i+1 $。
  • Subtask 6(15 pts):所有边的边权均为1。
  • Subtask 7(15 pts):无特殊限制。

子任务顺序与难度顺序无关。