CF2231E

· · 题解

伟大宋队的树上背包做法。

做法

想到树形 DP 是容易的，难点在于状态的定义和转移的细节。题目要求大小为 d，且有三个钦定点在选择块边缘。于是定义。

每个方案在其连通块深度最小点统计。答案为 \sum dp_{u,d,3}。

初始化每个点只选自己且钦定的方案，dp_{u,1,1}=1。

题目要求没有多余的选择，如果子树 u 内没有钦定点。是不能参与考虑的。考虑是否钦定 u 子树内除 v 以外的点。

如果钦定，那么枚举当前状态总选择点数 i。子树 v 内选择数 j。总钦定数 x，子树 v 内钦定数 y。

满足 i>j,x>y。

dp_{u,i,x}\gets dp_{v,j,y}\times dp_{u,i-j,x-y}

注意这是一个树上背包，复杂度是 O(n^2) 的，且树上背包要倒序枚举总和状态。

如果不钦定，那么相当于是在 v 的状态上多选了一个 u 且不钦定，转移到 u。枚举 v 子树所有状态，然后选择总数加一转移到 u 即可。

dp_{u,i+1,x}\gets dp_{v,i,x}

注意这个计算要在前一个转移后，以免后面转移要用的 DP 值，包含了 v 子树的状态。

总时间复杂度就是树上背包的 O(n^2)，实现即可。

代码

::::success[Accepted code]

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2020;
int n,d,ans;
int siz[N],dp[N][N][4];
vector<int>G[N];
void dfs(int u,int fa)
{
    for(auto v:G[u])
    {
        if(v==fa)continue;
        dfs(v,u);
    }
    dp[u][1][1]=1;
    siz[u]=1;
    for(auto v:G[u])
    {
        if(v==fa)continue;
        for(int i=siz[u]+siz[v];i>=2;i--)
        {
            for(int j=min(siz[v],i-1);j>=1;j--)
            {
                for(int x=2;x<=3;x++)
                {
                    for(int y=1;y<x;y++)
                    {
                        dp[u][i][x]=dp[u][i][x]+dp[u][i-j][y]*dp[v][j][x-y];
                    }
                }
            }
        }
        for(int j=1;j<=siz[v];j++)
        {
            for(int k=1;k<=2;k++)
            {
                dp[u][j+1][k]=dp[u][j+1][k]+dp[v][j][k];
            }
        }
        siz[u]+=siz[v];
    }
}
void clear()
{
    for(int i=1;i<=n;i++)G[i].clear();
    for(int i=1;i<=n;i++)siz[i]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            for(int k=1;k<=3;k++)
            {
                dp[i][j][k]=0;
            }
        }
    }
}
void solve()
{
    cin>>n>>d;
    for(int i=1;i<n;i++)
    {
        int u,v;cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1,0); 
    ans=0;
    for(int i=1;i<=n;i++)ans+=dp[i][d][3];
    cout<<ans<<"\n";
    clear();
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T;cin>>T;
    while(T--)solve();
    return 0;
}

::::