Submission #45683174

---

Source Code Expand

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
#define SIZE 100000
ll inv[SIZE+1];
ll kai[SIZE+1];
ll invkai[SIZE+1];
void invinit()
{
	inv[1] = 1;
	for (int i = 2; i <= SIZE; i++)
	{
		inv[i] = mod - (mod / i)*inv[mod%i] % mod;
	}
	kai[0] = invkai[0] = 1;
	for (int i = 1; i <= SIZE; i++)
	{
		kai[i] = kai[i - 1] * i%mod;
		invkai[i] = invkai[i - 1] * inv[i] % mod;
	}
}
ll com[222][222];
vector<int>pat[111];
bool flag[111];
ll dp[101][101][101];
ll zd[111][111];
ll zzzd[111][111];
int gen;
ll ans[111];
int dfs(int node,bool fff)
{
    flag[node]=true;
    int sz=0;
    dp[node][0][0]=1;
    for(int i=0;i<pat[node].size();i++)
    {
        int v=pat[node][i];
        if(flag[v])continue;
        int s=dfs(v,false);
        for(int j=0;j<=sz+s;j++)for(int k=0;k<=sz+s;k++)zd[j][k]=0;
        for(int j=0;j<=sz;j++)
        {
            for(int k=0;k<=s;k++)
            {
                for(int l=0;l<=sz;l++)
                {
                    for(int m=0;m<=s;m++)
                    {
                        if(dp[node][j][l]==0||dp[v][k][m]==0)continue;
                        zd[j+k][l+m]=(zd[j+k][l+m]+dp[node][j][l]*dp[v][k][m]%mod*com[j+k][j]%mod*com[sz+s-j-k][sz-j])%mod;
                    }
                }
            }
        }
        for(int j=0;j<=sz+s;j++)for(int k=0;k<=sz+s;k++)dp[node][j][k]=zd[j][k];
        sz+=s;
    }
    /*printf("++++%d\n",node+1);
    for(int i=0;i<=sz;i++)
    {
        for(int j=0;j<=sz;j++)
        {
            printf("%lld ",dp[node][i][j]);
        }
        printf("\n");
    }
    printf("\n");*/
    if(fff)
    {
        for(int i=0;i<=sz;i++)
        {
            for(int j=gen;j<=sz;j++)
            {
                ans[node]=(ans[node]+dp[node][i][j])%mod;
            }
        }
    }
    for(int i=0;i<=sz+1;i++)for(int j=0;j<=sz+1;j++)zzzd[i][j]=0;
    for(int k=0;k<=sz;k++)
    {
        for(int i=0;i<=sz;i++)
        {
            for(int j=0;j<=sz;j++)
            {
                if(k<=i)
                {
                    zzzd[i+1][0]+=dp[node][i][j];
                }
                if(k>=i)
                {
                    zzzd[i][j+1]+=dp[node][i][j];
                }
            }
        }
    }
    for(int i=0;i<=sz+1;i++)for(int j=0;j<=sz+1;j++)dp[node][i][j]=zzzd[i][j]%mod;
    /*for(int i=0;i<=sz+1;i++)
    {
        for(int j=0;j<=sz+1;j++)
        {
            printf("%lld ",dp[node][i][j]);
        }
        printf("\n");
    }*/
    return sz+1;
}
int main()
{
    int num;
    scanf("%d%d",&num,&gen);
    invinit();
    for(int i=0;i<num-1;i++)
    {
        int za,zb;
        scanf("%d%d",&za,&zb);
        za--,zb--;
        pat[za].push_back(zb);
        pat[zb].push_back(za);
    }
    for(int i=0;i<111;i++)
    {
        com[i][0]=1;
        for(int j=1;j<=i;j++)com[i][j]=(com[i-1][j-1]+com[i-1][j])%mod;
    }
    ll s=0;
    for(int i=0;i<num;i++)
    {
        //printf("------root: %d\n",i+1);
        fill(flag,flag+num,false);
        for(int j=0;j<=num;j++)for(int k=0;k<=num;k++)for(int l=0;l<=num;l++)dp[i][j][k]=0;
        dfs(i,true);
        //printf("ans: %lld\n",ans[i]);
        s=(s+ans[i])%mod;
    }
    printf("%lld\n",s*invkai[num]%mod);
}

Submission Info

Compile Error

Main.cpp: In function ‘int dfs(int, bool)’:
Main.cpp:38:18: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   38 |     for(int i=0;i<pat[node].size();i++)
      |                 ~^~~~~~~~~~~~~~~~~
Main.cpp: In function ‘int main()’:
Main.cpp:113:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  113 |     scanf("%d%d",&num,&gen);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
Main.cpp:118:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  118 |         scanf("%d%d",&za,&zb);
      |         ~~~~~^~~~~~~~~~~~~~~~

Judge Result