Logo Universal Online Judge

UOJ

时间限制:3 s 空间限制:512 MB

#2996. 染色(black)

统计

$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