4482: 「2018 集训队互测 Day 3」白云的旅行
内存限制：1024 MB
时间限制：3.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
白云开始了一段旅程。
旅途中一共有 $n$ 个城市，编号为 $1$ 到 $n$，城市之间有一些道路相连。其道路结构可以抽象为一棵仙人掌。如果一个无向连通图的任意一条边最多属于一个简单环，我们就称之为仙人掌。所谓简单环即不经过重复的结点的环。
白云对这些城市间的每条道路都有一个喜爱度。一条路径的喜爱度是其上所有道路的喜爱度的乘积。 现在白云在 $1$ 号城市准备出发。为了制定合理的路线，白云会时不时问白兔：“从 $1$ 号城市出发**不经过重复道路**到达 $k$ 号城市的所有路径喜爱度之和是多少？” 这可难倒了白兔，请你帮忙对于 $k=1,2,\ldots,n$ 求出相应答案。
只需要输出答案对$998244353( = 7\times 17\times 223+1,$一个质数$)$取模后的值。
白云对这些城市间的每条道路都有一个喜爱度。一条路径的喜爱度是其上所有道路的喜爱度的乘积。 现在白云在 $1$ 号城市准备出发。为了制定合理的路线，白云会时不时问白兔：“从 $1$ 号城市出发**不经过重复道路**到达 $k$ 号城市的所有路径喜爱度之和是多少？” 这可难倒了白兔，请你帮忙对于 $k=1,2,\ldots,n$ 求出相应答案。
只需要输出答案对$998244353( = 7\times 17\times 223+1,$一个质数$)$取模后的值。
输入
第 $1$ 行两个正整数 $n,m$ 表示城市的个数和道路的条数。保证 $n \ge 2$。
接下来 $m$ 行每行两个正整数 $v,u,w(1 \le v,u \le n,1 \le w < 998244353)$ 表示一条连接城市 $v$ 和 $u$ 的喜爱度为 $w$ 的道路。 保证输入的图是一棵仙人掌，没有自环，但可能有重边。
输出
输出 $n$ 行，第 $i$ 行包含一个整数表示 $k=i$ 时的答案。
样例输入 复制
11 11
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 1 1
2 7 10
3 8 20
4 9 30
5 10 40
6 11 50样例输出 复制
3
2
2
2
2
2
20
40
60
80
100提示
数据范围：对于所有数据，$n \le 10^5,1 \le w < 998244353$。 | 子任务编号 | $n \leq$ | $w \leq$ | 其它约定 | | ----- | ------- | ------ | ------ | | 1 | $10^5$ | $1$ | $m=n-1$ | | 2 | $10^5$ | $998244352$ | $m=n-1$ | | 3 | $8$ | $998244352$ | | | 4 | $10^5$ | $1$ | 一个点最多只在一个环中 | | 5 | $10^5$ | $998244352$ | 一个点最多只在一个环中 | | 6 | $500$ | $998244352$ | | | 7 | $3000$ | $1$ | | | 8 | $3000$ | $998244352$ | | | 9 | $10^5$ | $1$ | | | 10 | $10^5$ | $998244352$ | | | 虽然我没有给 $m$ 的范围，但是熟悉仙人掌的小朋友都知道对于仙人掌肯定满足 $n-1 \le m \le 2n-2$。