AtCoder

Problem Statement

One day, Takahashi was given the following problem from Aoki:

You are given a tree with N vertices and an integer K. The vertices are numbered 1 through N. The edges are represented by pairs of integers (a_i,b_i).
For a set S of vertices in the tree, let f(S) be the minimum number of the vertices in a subtree of the given tree that contains all vertices in S.
There are ways to choose K vertices from the trees. For each of them, let S be the set of the chosen vertices, and find the sum of f(S) over all ways.
Since the answer may be extremely large, print it modulo 924844033(prime).

Since it was too easy for him, he decided to solve this problem for all K=1,2,…,N.

Constraints

2≦N≦200,000
1≦a_i,b_i≦N
The given graph is a tree.

Input

The input is given from Standard Input in the following format:

N
a₁ b₁
a₂ b₂
:
a_N−1 b_N−1

Output

Print N lines. The i-th line should contain the answer to the problem where K=i, modulo 924844033.

Sample Input 1

3
1 2
2 3

Sample Output 1

3
7
3

The diagram above illustrates the case where K=2. The chosen vertices are colored pink, and the subtrees with the minimum number of vertices are enclosed by red lines.

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

7
67
150
179
122
45
7


    考虑每条边的贡献，对于k==i的答案显然会贡献 C(n,i) - C(s,i) - C(n-s,i) ，其中s是边一端的子树大小。
    这玩意暴力算显然是 O(N^2) 的，想一想还可以怎么优化。
    
    显然每条边的第一项 C(n,i) 是常量，我们最后对于每个i加上即可；
    后面的组合数可以拆成 阶乘和阶乘的逆的乘积的形式，所以我们就可以构造两个多项式：
A = ∑ cnt[s] * x^s   (cnt[s] 是 子树大小为s的子树个数)
B = Σ 1/(i!) * x^(-i)
    这两个多项式卷出来就可以得到每个k==i的答案(别忘了每个位置再乘一个阶乘的逆元)

     (只有我一个人被模数坑了吗QWQ)

/*
    对于一条把树分成s和n-s的边
	C(s,k) -> s! / k! / (s-k)!
	C(n-s,k) -> (n-s)! / k! / (n-s-k)! 
*/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=600005,ha=924844033,root=5;
inline int add(int x,int y){ x+=y; return x>=ha?x-ha:x;}
inline void ADD(int &x,int y){ x+=y; if(x>=ha) x-=ha;}

inline int ksm(int x,int y){
	int an=1;
	for(;y;y>>=1,x=x*(ll)x%ha) if(y&1) an=an*(ll)x%ha;
	return an;
}

int jc[maxn+5],ni[maxn+5],n,m,ans,to[maxn*2],ne[maxn*2],num,inv;
int a[maxn+5],b[maxn+5],r[maxn+5],siz[maxn+5],hd[maxn],N,l,INV;

inline void addline(int x,int y){ to[++num]=y,ne[num]=hd[x],hd[x]=num;}

inline int C(int x,int y){ return x<y?0:jc[x]*(ll)ni[y]%ha*(ll)ni[x-y]%ha;}

inline void init(){
	jc[0]=1;
	for(int i=1;i<=maxn;i++) jc[i]=jc[i-1]*(ll)i%ha;
	ni[maxn]=ksm(jc[maxn],ha-2);
	for(int i=maxn;i;i--) ni[i-1]=ni[i]*(ll)i%ha;
}

void dfs(int x,int fa){
	siz[x]=1;
	for(int i=hd[x];i;i=ne[i]) if(to[i]!=fa) dfs(to[i],x),siz[x]+=siz[to[i]];
	if(x!=1) ADD(a[siz[x]],jc[siz[x]]),ADD(a[n-siz[x]],jc[n-siz[x]]);
}

inline void NTT(int *c,int f){
	for(int i=0;i<N;i++) if(i<r[i]) swap(c[i],c[r[i]]);
	
	for(int i=1;i<N;i<<=1){
		int omega=ksm(f==1?root:inv,(ha-1)/(i<<1));
		for(int j=0,P=i<<1;j<N;j+=P){
			int now=1;
			for(int k=0;k<i;k++,now=now*(ll)omega%ha){
				int x=c[j+k],y=c[j+k+i]*(ll)now%ha;
				c[j+k]=add(x,y);
				c[j+k+i]=add(x,ha-y);
			}
		}
	}
	
	if(f==-1) for(int i=0;i<N;i++) c[i]=c[i]*(ll)INV%ha;
}

inline void solve(){
	dfs(1,1);
	for(int i=0;i<n;i++) b[n-i]=ni[i];
	
	for(N=1;N<=(2*n);N<<=1) l++;
	for(int i=0;i<N;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
	
	NTT(a,1),NTT(b,1);
	for(int i=0;i<N;i++) a[i]=a[i]*(ll)b[i]%ha;
	INV=ksm(N,ha-2),NTT(a,-1);
	
	for(int i=1;i<=n;i++) a[i+n]=add(ha-a[i+n]*(ll)ni[i]%ha,C(n,i)*(ll)n%ha);
}

int main(){
//	freopen("data.in","r",stdin);
//	freopen("data.out","w",stdout);
	
	init(),inv=ksm(5,ha-2);
	
	scanf("%d",&n);
	
	int uu,vv;
	for(int i=1;i<n;i++) scanf("%d%d",&uu,&vv),addline(uu,vv),addline(vv,uu);
	
	solve();
	
	for(int i=1;i<=n;i++) printf("%d
",a[i+n]);
	return 0;
}