agc005f

题意：给出一棵n个点的树和K，从树中选出K个点，设点集为S，设f(S)为将这个点集中的点在树中联通联通块的最小点数。对于1到n的每一个K，求$$C_n^K$$种选法的f(S)之和。

对于每条边计算贡献，设边的一边有ai个点，那么贡献为$$C_n^K-C_{ai}^K-C_{n-ai}^K$$，$$C_n^K$$直接计算，$$C_{n-ai}^K$$与$$C_{ai}^K$$计算同理。
$$C_{ai}^K=\\frac{ai!}{K!(ai-K)!}$$
其中$$\\frac{1}{K!}$$可以最后乘，$$\frac{ai!}{(ai-K)!}$$将分母翻转成为卷积的形式。NTT处理即可

#include <bits/stdc++.h>
using namespace std;
#define N 210000
#define mod 924844033
#define ll long long
#define g 5
int n,tot,len;
int head[N],nex[N<<1],to[N<<1];
int size[N],jc[N],njc[N],ans[N];
int a[N<<2],b[N<<2],c[N<<2];
int qpow(int x,int y)
{
    int ret=1;
    while(y)
    {
        if(y&1)ret=(ll)ret*x%mod;
        x=(ll)x*x%mod;y>>=1;
    }
    return ret;
}
void init()
{
    jc[0]=njc[0]=1;
    for(int i=1;i<=n;i++)jc[i]=(ll)jc[i-1]*i%mod;
    njc[n]=qpow(jc[n],mod-2);
    for(int i=n-1;i>=1;i--)njc[i]=(ll)njc[i+1]*(i+1)%mod;
    for(len=1;len<(n+1)*2;len<<=1);
}
void add(int x,int y)
{
    tot++;
    nex[tot]=head[x];head[x]=tot;
    to[tot]=y;
}
void dfs(int x,int y)
{
    size[x]=1;
    for(int i=head[x];i;i=nex[i])
        if(to[i]!=y)
        {
            dfs(to[i],x);
            size[x]+=size[to[i]];
        }
}
int C(int x,int y){return (ll)jc[x]*njc[y]%mod*njc[x-y]%mod;}
void NTT(int *a,int len,int type)
{
    for(int i=0,t=0;i<len;i++)
    {
        if(i<t)swap(a[i],a[t]);
        for(int j=len>>1;(t^=j)<j;j>>=1);
    }
    for(int i=2;i<=len;i<<=1)
    {
        int wn=qpow(g,(mod-1)/i);
        for(int j=0;j<len;j+=i)
        {
            int w=1,t;
            for(int k=0;k<i>>1;k++,w=(ll)w*wn%mod)
            {
                t=(ll)w*a[j+k+(i>>1)]%mod;
                a[j+k+(i>>1)]=(a[j+k]-t+mod)%mod;
                a[j+k]=(a[j+k]+t)%mod;
            }
        }
    }
    if(type==-1)
    {
        for(int i=1;i<len>>1;i++)swap(a[i],a[len-i]);
        int t=qpow(len,mod-2);
        for(int i=0;i<len;i++)a[i]=(ll)a[i]*t%mod;
    }
}
int main()
{
    //freopen("tt.in","r",stdin);
    scanf("%d",&n);
    init();
    for(int i=1,x,y;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    }
    dfs(1,0);
    for(int i=1;i<=n;i++)
        ans[i]=(ll)n*C(n,i)%mod;
    for(int i=2;i<=n;i++)(a[size[i]]+=jc[size[i]])%=mod;
    for(int i=0;i<=n;i++)b[i]=njc[n-i];
    NTT(a,len,1);NTT(b,len,1);
    for(int i=0;i<len;i++)c[i]=(ll)a[i]*b[i]%mod;
    NTT(c,len,-1);
    for(int i=1;i<=n;i++)
    {
        c[n+i]=(ll)c[n+i]*njc[i]%mod;
        ans[i]=(ans[i]-c[n+i]+mod)%mod;
    }

    memset(a,0,sizeof(a));
    for(int i=2;i<=n;i++)
    {   
        size[i]=n-size[i];
        (a[size[i]]+=jc[size[i]])%=mod;
    }
    NTT(a,len,1);
    for(int i=0;i<len;i++)c[i]=(ll)a[i]*b[i]%mod;
    NTT(c,len,-1);
    for(int i=1;i<=n;i++)
    {
        c[n+i]=(ll)c[n+i]*njc[i]%mod;
        ans[i]=(ans[i]-c[n+i]+mod)%mod;
    }
    for(int i=1;i<=n;i++)
        printf("%d\n",ans[i]);
    return 0;
}