1 条题解

  • 0
    @ 2026-4-1 18:48:02
    #include<bits/stdc++.h>
    using namespace std;
    #define int long long
    const int N=5010,P=998244353;
    int dp[N][N][2],dp1[N][2],siz[N],n;vector<int>G[N];
    void dfs(int x,int f)
    {
    	dp[x][0][0]=dp[x][1][1]=1;siz[x]=1;
    	for(int y:G[x])if(y!=f)
    	{
    		dfs(y,x);
    		for(int i=0;i<=siz[x];i++)for(int j=0;j<=siz[y];j++)if(i+j-1<=n)
    		{
    			dp1[i+j][0]=(dp1[i+j][0]+dp[x][i][0]*dp[y][j][0])%P;
    			dp1[i+j][0]=(dp1[i+j][0]+dp[x][i][0]*dp[y][j][1])%P;
    			dp1[i+j][1]=(dp1[i+j][1]+dp[x][i][1]*dp[y][j][0])%P;
    			if(i+j-1>=0)dp1[i+j-1][1]=(dp1[i+j-1][1]+dp[x][i][1]*dp[y][j][1])%P;
    		}
    		for(int i=0;i<=n;i++)
    			dp[x][i][0]=dp1[i][0],dp[x][i][1]=dp1[i][1],
    			dp1[i][0]=dp1[i][1]=0;
    		siz[x]+=siz[y];
    	}
    }
    signed main()
    {
    	cin>>n;
    	for(int i=1;i<n;i++)
    	{
    		int x,y;cin>>x>>y;
    		G[x].push_back(y);
    		G[y].push_back(x);
    	}
    	dfs(1,0);
    	for(int i=1;i<=n;i++)cout<<(dp[1][i][0]+dp[1][i][1])%P<<'\n';
    	return 0;
    }
    • 1

    信息

    ID
    7780
    时间
    2000ms
    内存
    1024MiB
    难度
    10
    标签
    递交数
    6
    已通过
    2
    上传者