#P9610. Many Easy Problems

    ID: 6225 传统题 5000ms 512MiB 尝试: 2 已通过: 2 难度: 8 上传者: 标签>CF2400提高+/省选-贡献法补集计数阶乘逆元预处理卷积转化NTT

Many Easy Problems

题目描述

给定一棵大小为 nn 的无根树,定义 f(i)f(i) 为对于所有大小为 ii 的点集,能够包含该点集的最小连通块大小之和。

对于每一个 i=1→ni=1\to n,求出 f(i)f(i) 对 924844033924844033 取模的值,该质数的原根为 55。

输入格式

第一行为一个整数 nn。

接下来 n−1n-1 行,一行两个整数 ui,viu_i,v_i,表示一条树上的边。

输出格式

共 nn 行,第 ii 行输出 f(i)f(i) 对 924844033924844033 取模的值。

样例

3
1 2
2 3
3
7
3

当 i=2i=2 时,解释如下图,其中被染粉的点表示被选择出的点集,红圈为包含它的最小连通块:

fT9Otx.png

4
1 2
1 3
1 4
4
15
13
4
7
1 2
2 3
2 4
4 5
4 6
6 7
7
67
150
179
122
45
7

数据范围

对于所有数据,满足 2≤n≤2×1052\le n\le 2\times 10^5。