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<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#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<n;i++) {

        int a,b;scanf("%d%d",&a,&b);insert(a,b);insert(b,a);

    }

    dfs(1,0);

    for(int i=k;i<=n;i++)ans+=dp[1][i],ans%=mod;

    printf("%lld",ans);

    return 0;

}

巴特西

51Nod1353 树

51Nod1353 树

思路

代码

最新文章

热门文章