#1794. 意念力

    ID: 1794 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1421来源:qoj.ac数据:公开样例递归记忆化搜索

意念力

意念力

题目描述

标题: 意念力 - Problem - QOJ.ac

Statistics

The problem was used in the following contests:

我曾经也像你一样果冻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≤n≤100000,1≤k≤1014,1≤x,y≤n,1≤z≤109。

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

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

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

5 2
1 2 1
1 3 1
2 4 1
2 5 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
0 0 0 16 308 836 674 206 25 1