蓝魔法师

题意：
给与一棵树，求有多少种删边方案，使得删后的图每个连通块大小小于等于k，两种方案不同当且仅当存在一条边在一个方案中被删除，而在另一个方案中未被删除，答案对998244353取模。

思路：
树形dp：
从叶子节点向根转移，dp[i][j]表示以i为根的树删边时i处于的连通块大小为j的方案数。
sum[i]表示以i为根的树使得删后的图每个连通块大小小于等于k的总方案数。
sz[i]表示以i为根的树的节点数。
当儿子v向父亲u转移时有两种情况：
①父子节点在同一连通块：
dp[u][i+j]+=dp[u][i]*dp[v][j];
①父子节点不在同一连通块：
dp[u][i]=dp[u][i] * sum[v];
注意先用一个中间变量保存，防止重复。
最后结果为sum[root].

代码：

#include <bits/stdc++.h>
typedef long long ll;

using namespace std;

const ll inf=998244353;

inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

int n, k ,sz[2005];
ll dp[2005][2005], pa[2005];
ll sum[2005], ans=0;
vector<int> g[2005];

void dfs(int v,int f)
{
    dp[v][1]=1;
    sz[v]=1;
    for(int i=0; i<g[v].size(); i++)
    {
        if(g[v][i]!=f)
        {
            dfs(g[v][i],v);
            for(int j=min(k,sz[v]); j; j--)
            {
                for(int o=min(sz[g[v][i]],k); o; o--)
                {
                    if(j+o<=k)
                    {
                        pa[j+o]=(pa[j+o]+dp[v][j]*dp[g[v][i]][o]%inf)%inf;
                    }
                }
                pa[j]=(pa[j]+dp[v][j]*sum[g[v][i]]%inf)%inf;
            }
            sz[v]+=sz[g[v][i]];
            for(int j=1; j<=min(k,sz[v]); j++)
            {
                dp[v][j]=pa[j]%inf;
                pa[j]=0;
            }
        }
    }
    for(int i=1; i<=min(k,sz[v]); i++)
    {
        sum[v]=(sum[v]+dp[v][i])%inf;
    }
    return ;
}

int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1; i<n; i++)
    {
        int u, v;
        scanf("%d%d",&u,&v);
        g[v].push_back(u);
        g[u].push_back(v);
    }
    dfs(1,-1);
    cout << sum[1] << endl;
    return 0;
}