S 老师的虚树
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

作为树的大师，S 老师又给你了一个数学题：

一棵树 T 可以表示为 T = (V, E)，其中 V 表示点集，E 表示边集，并且满足 |V|=n,|E|=|V|-1。在本题中，每条边 (u,v) 还有一个颜色 c(u,v)。

对于 V 的一个子集 S，其关于 T 的虚树是包含所有 S 中顶点的最小连通子图。

形式化地，当且仅当满足以下所有条件时，T'=(V',E') 是 S 关于 T 的虚树：

  • S\subseteq V'\subseteq V, E'\subseteq E
  • E'=\{(u,v) \mid u\in V',v\in V',(u,v)\in E\}
  • T' = (V',E') 是连通的。
  • |V'| 在所有可能的情况中最小。

对于 S 的虚树 T'=(V',E')，其权值 w(S) 定义为 T 中不同边颜色数量。形式化地，w(S) = |\{c(e)\mid e\in E'\}|。

现在，给定 T，对于 i=1,2,...,n，请计算大小为 i 的顶点子集权值的期望，对 998244353 取模。即，第 i 个输出应为 \frac{\sum_{|S|=i} w(S)}{\binom{|T|}{i}} \bmod 998244353.

输入描述:

第一行包含一个整数 n\ (2\leq n\leq 2\cdot 10^5)，表示树 T 中的顶点数。

接下来的 n-1 行，每行包含三个整数 u,v,c\ (1\leq u,v,c\leq n,u\not = v)，表示 u 和 v 之间有一条颜色为 c 的边。保证给定的图是一棵合法的树。

输出描述:

一行 n 个数，第 i 个数表示 \frac{\sum_{|S|=i} w(S)}{\binom{|T|}{i}} \bmod 998244353。

可以证明答案始终可以表示为不可约分数 \frac ab，其中 b\bmod 998244353 \neq 0，故你只需输出 a\cdot b^{-1} \bmod 998244353。
示例1

输入

复制 
3
3 2 3
2 1 1

输出

复制 
0 332748119 2
示例2

输入

复制 
5
5 1 5
2 1 3
4 1 4
3 2 2

输出

复制 
0 399297743 99824438 199648874 4