$n$ 个节点的树,对每个节点设为根求:
枚举剩下 $n-1$ 个节点的顺序 $a_1,a_2\cdots a_{n-1}$ 并求和:
初始只有根为黑色,从 $1$ 到 $n-1$ 枚举 $i$,将 $a_i$ 到根的路径染黑,并把黑色节点数加入答案。
对 998244353
取模。
输入格式
第一行一个整数 $n$。
接下来 $n-1$ 行,每行两个整数 $u_i,v_i$,表示一条树边。
输出格式
$n$ 行,第 $i$ 行输出节点 $i$ 为根时的答案。
样例输入1
5
1 2
1 3
2 4
2 5
样例输出1
366
356
402
392
392
样例 2-3
见下发文件。
数据范围及限制
对于所有数据 $2\leq n\leq 10^6$。
子任务编号 | $n\leq$ | 分值 |
---|---|---|
1 | 9 | 5 |
2 | 18 | 6 |
3 | 100 | 8 |
4 | 300 | 12 |
5 | 3000 | 20 |
2 | $10^5$ | 36 |
7 | $10^6$ | 13 |