1 条题解

  • 0
    @ 2026-4-3 13:44:02
    #include<bits/stdc++.h>
    using namespace std;
    #define int long long
    const int N=3010,P=998244353;
    vector<int>G[N];
    int dp[N][N][2],dp1[N][2],s[N][2];
    void dfs(int x,int f)
    {
    	dp[x][0][0]=1;dp[x][1][1]=(x!=1);int siz=(x!=1);
    	for(int y:G[x])if(y!=f)
    	{
    		dfs(y,x);siz++;
    		for(int i=0;i<=siz;i++)
    		{
    			dp1[i][0]=dp[x][i][0]*s[y][0]%P;
    			dp1[i][1]=dp[x][i][1]*s[y][0]%P;
    			if(i>0)
    			{
    				dp1[i][0]=(dp1[i][0]+dp[x][i-1][0]*i%P*s[y][1])%P;
    				dp1[i][1]=(dp1[i][1]+dp[x][i-1][1]*i%P*s[y][1])%P;
    			}
    		}
    		for(int i=0;i<=siz;i++)
    			dp[x][i][0]=dp1[i][0],dp1[i][0]=0,
    			dp[x][i][1]=dp1[i][1],dp1[i][1]=0;
    	}
    	for(int i=0;i<=siz;i++)
    		s[x][0]+=dp[x][i][0],s[x][1]+=dp[x][i][1],
    		s[x][0]%=P,s[x][1]%=P;
    }
    signed main()
    {
    	int n;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);
    	cout<<s[1][0];
    	return 0;
    }
    • 1

    信息

    ID
    1160
    时间
    2000ms
    内存
    1024MiB
    难度
    8
    标签
    递交数
    60
    已通过
    11
    上传者