51Nod1353 树

思路

我们定义\(dp[i][j]\)代表第i个点联通块大小为j的方案总数，也可以把它理解为等待分配（不确定归属）的联通块大小为j的方案总数。

那么每次转移我们就使用一个类似背包的东西来统计答案。

对于一个节点的每个儿子，我们只需要从大到小遍历所有可用的j_now（j_now上限就是所有遍历过的点子树大小的和）。然后再枚举这个儿子的j_son，那么显然我们就获得了很多第i个点联通块大小为j_son+j_now的方案。dp[i][j_son+j_now]+=dp[i][j_now]*dp[son][j_son]累计一下答案即可。需要注意的是，j_now需要从大往小遍历，因为反过来的话方案会算重（自己想一下01背包和完全背包）。另外，j_son是可以为0的，dp[son][0]代表son这个点只会包含在son子树内的联通块。所以对于每一个j_now都需要dp[now][j_now]*=dp[son][0]。

在状态转移完后，对于每一个\(j\geq k\)我们都要执行操作dp[now][0]+=dp[now][j]。相当于分了一块大小为j的联通块。想一想就知道为什么了。

其实就是道树形依赖背包的模版。

代码

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define ll long long#define maxn 2050#define mod (int)(1e9+7)using namespace std;ll dp[maxn][maxn],ans;int head[maxn],cnt,n,k,size[maxn];struct gg {    int u,v,next;}side[maxn*2];void insert(int u,int v) {    struct gg add={u,v,head[u]};side[++cnt]=add;head[u]=cnt;}void dfs(int now,int fa) {    size[now]=1;    dp[now][1]=1;    for(int i=head[now];i;i=side[i].next) {        int v=side[i].v;if(v==fa)continue;        dfs(v,now);        for(int j1=size[now];j1>=1;j1--) {            for(int j2=1;j2<=size[v];j2++) {                dp[now][j1+j2]+=(dp[now][j1]*dp[v][j2])%mod;dp[now][j1+j2]%=mod;            }            dp[now][j1]*=dp[v][0];dp[now][j1]%=mod;        }        size[now]+=size[v];    }    for(int i=k;i<=size[now];i++)dp[now][0]+=dp[now][i],dp[now][0]%=mod;}int main() {    scanf("%d%d",&n,&k);    for(int i=1;i