1 条题解

  • 1
    @ 2023-8-3 17:25:32

    image

    #include <bits/stdc++.h>
    #define mod 998244353 
    #define ll long long
    using namespace std;
    const int N=5005;
    int n,m,k,s,t,sz[N];
    ll f[N][N],g[N];
    vector<int> e[N];
    void dfs(int u,int fa){
    	sz[u]=1;f[u][0]=1;
    	for (int &v:e[u]){
    		if (v==fa) continue;
    		dfs(v,u);
    		memset(g,0,sizeof(g));
    		for (int i=min(sz[u],m);i>=0;--i)
    			for (int j=0;j<=sz[v];++j){
    				g[i]=(g[i]+f[u][i]*f[v][j])%mod;//断开
    				if (i+j+1<=m) g[max(i,j+1)]=(g[max(i,j+1)]+f[u][i]*f[v][j])%mod;//不断开
    			}
    		sz[u]+=sz[v];
    		for (int i=0;i<=min(sz[u],m);++i) f[u][i]=g[i];
    	}
    }
    int main(){
    	cin>>n>>m;
    	for (int i=1;i<n;++i){
    		cin>>s>>t;
    		e[s].push_back(t);
    		e[t].push_back(s);
    	}
    	dfs(1,0);
    	ll ans=0;
    	for (int i=0;i<=m;++i) ans=(ans+f[1][i])%mod;
    	cout<<ans<<"\n";
    }
     
    
    • 1

    信息

    ID
    374
    时间
    1000ms
    内存
    256MiB
    难度
    2
    标签
    (无)
    递交数
    27
    已通过
    22
    上传者