Submission #69903945

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
using namespace std;
const int N = 5005,mod = 998244353;
int siz[N],hd[N],cnt,n;
ll inv[N],f[N][N],ans;
struct node{int to,nex;}e[N << 1];
inline void add(int u,int v)
{e[++cnt] = {v,hd[u]};hd[u] = cnt;}
void dfs(int u,int fa)
{
    f[u][1] = 1;siz[u] = 1;
    for(int i = hd[u],v;i;i = e[i].nex)if((v = e[i].to) != fa)
    {
        dfs(v,u);
        for(int j = siz[u];j;j--)
        {
            ll s = f[u][j];f[u][j] = 0;
            for(int k = 1;k <= siz[v];k++)
            {
                ll x = s*f[v][k]%mod*inv[k];
                (f[u][j+k] -= x) %= mod;
                (f[u][j] += x) %= mod;
            }
        }
        siz[u] += siz[v];
    }
    for(int j = 1;j <= siz[u];j++)(f[u][j] *= inv[j]) %= mod;
}
char buf[1<<21],*p1,*p2;
inline int rd()
{
    char c;int f = 1;
    while(!isdigit(c = getchar()))if(c=='-')f = -1;
    int x = c-'0';
    while(isdigit(c = getchar()))x = x*10+(c^48);
    return x*f;
}
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    n = rd();inv[1] = 1;
    for(int i = 2;i < N;i++)inv[i] = (mod-mod/i)*inv[mod%i]%mod;
    for(int i = 1;i < n;i++)
    {int u = rd(),v = rd();add(u,v);add(v,u);}
    dfs(1,0);
    for(int i = 1;i <= n;i++)(ans += f[1][i]) %= mod;
    printf("%lld\n",(ans+mod)%mod);
    return 0;
}

Submission Info

Judge Result