「做题笔记」树上背包
|
957
|
0
|
c++,OI,题解

3264 字
|
39 分钟

这类题感觉相对是比较套路的，但实际写起来坑点比较多，如需要控制好枚举的上下界，以及要考虑新状态是否会被覆盖等问题。

一般来说，大多数树上背包都是 01 背包，因此转移时要注意好内外层循环枚举的方向，以及确保新状态不被覆盖和不会重复考虑，为了避免上面的情况通常可以使用一个 tmp 数组将答案暂存下来，转移完再对 dp 数组进行更新（也可以转移前就存下来）。

此类问题的复杂度一般是 $\mathcal{O}(n^2)$，直观理解是因为任意两个点只会在其 lca 处匹配一次，所以是 $\mathcal{O}(n^2)$。要保证复杂度的正确性，还要注意控制 dp 枚举的上下界，如果没控制好，可能会被一条链的数据卡到 $\mathcal{O}(n^3)$。

本文中统一用 $x$ 表示当前节点，$to$ 表示其儿子节点。

二叉苹果树

一道模板题。设 $dp[x][i]$ 表示表示 $x$ 的子树内保留 $i$ 条边，至多保留的苹果数目。不难发现，如果我们想要保留一条边，那么必须保留从根节点到这条边路径上的所有边，所以可以得出状态转移方程：

$$dp[x][i]=max(dp[x][i],dp[x][i-j-1]+dp[to][j]+v)$$

其中 $i-j-1$ 而不是 $i-j$ 正是因为我们必须要保留当前到儿子的边才能连到子树内的边。

code：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 150, mod = 1e9 + 7, INF = 1e9;
vector<pair<int,int>> g[maxn];
int dp[maxn][maxn];
int siz[maxn];
int n,m;

void dfs(int x,int fa){
    for(auto &[to,v]:g[x]){
        if(to==fa)continue;
        dfs(to,x);
        siz[x]+=siz[to]+1;
        for(int i=min(siz[x],m);i>=0;i--){
            for(int j=min(siz[to],i-1);j>=0;j--){
                dp[x][i]=max(dp[x][i],dp[x][i-j-1]+dp[to][j]+v);
            }
        }
    }
}

void solve(){
    cin>>n>>m;

    for(int i=1;i<n;i++){
        int x,y,v;
        cin>>x>>y>>v;
        g[x].push_back({y,v});
        g[y].push_back({x,v});
    }
    dfs(1,0);
    cout<<dp[1][m]<<'\n';
}

signed main() {
    ios::sync_with_stdio(0);
    int t = 1;
    // cin>>t;
    while (t--) {
        solve();
    }

    return 0;
}

有线电视网

设 $dp[x][i]$ 表示在以 $x$ 为根的子树内选取 $i$ 个叶子节点（用户）能够获得的最大价值。

不那得出状态转移方程

$$dp[x][i]=max(dp[x][i],dp[x][i-j]+dp[to][j]-w)$$

初始化叶子节点的状态 $dp[x][1] = a[x]$ 即可。

#include<bits/stdc++.h>
using namespace std;
const int inf=-0x3f3f3f3f;
const int maxn=3005;
int n,m;
vector<pair<int,int>> g[maxn];
int dp[maxn][maxn];
int a[maxn];
int siz[maxn];

void dfs(int x){
    if(g[x].size()==0){
        dp[x][1]=a[x-n+m];
        siz[x]=1;
        return;
    }
    for(auto &[to,w]:g[x]){
        dfs(to);
        siz[x]+=siz[to];
        for(int j=siz[x];j>=0;j--){
            for(int k=0;k<=min(siz[to],j);k++){
                dp[x][j]=max(dp[x][j],dp[x][j-k]+dp[to][k]-w);
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(0);
    memset(dp,inf,sizeof(dp));
    cin>>n>>m;

    for(int i=1;i<=n-m;i++){
        int k,x,v;
        cin>>k;
        for(int j=1;j<=k;j++){
            cin>>x>>v;
            g[i].push_back({x,v});
        }
    }
    for(int i=1;i<=m;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++)dp[i][0]=0;
    dfs(1);
    for(int i=m;i>=0;i--){
        if(dp[1][i]>=0){
            cout<<i<<endl;
            return 0;
        }
    }
    return 0;
}

树上染色

注意到，每一条边的被路径经过的次数为边两侧同色点个数的乘积，即

$$cnt=(siz[to]-m)(n-k-siz[to]+m)+m(k-m)$$

其中 $siz[to]$ 表示子树大小，$m$ 表示子树内选的黑点数。那么每一条边的贡献就是 $cnt*w$。

设 $dp[x][i]$ 表示在以 $x$ 为根的子树内选取 $i$ 个点染成黑色的最大收益。于是得到状态转移方程为

$$dp[x][i]=max(dp[x][i],dp[x][i-m]+dp[to][m]+cnt*w)$$

注意这题要上下界优化，不然会被一条链的数据卡。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2005,INF=0x3f3f3f3f;
int _;
int n,k;
vector<pair<int,int>> g[maxn];
ll dp[maxn][maxn];
int siz[maxn];

void dfs(int x,int fa){
    siz[x]=1;
    dp[x][0]=dp[x][1]=0;
    for(auto &[to,w]:g[x]){
        if(to==fa)continue;
        dfs(to,x);
        siz[x]+=siz[to];
        for(int i=min(k,siz[x]);i>=0;i--){ 
            for(int m=max(0,i-siz[x]+siz[to]);m<=min(i,siz[to]);m++){
                if(dp[x][i-m]==-1)continue;
                dp[x][i]=max(dp[x][i],dp[x][i-m]+dp[to][m]+1ll*(n-k-siz[to]+m)*(siz[to]-m)*w+1ll*(k-m)*m*w);
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(0);
    memset(dp,-1,sizeof dp);
    cin>>n>>k;

    for(int i=1;i<n;i++){
        int x,y,z;
        cin>>x>>y>>z;
        g[x].push_back({y,z});
        g[y].push_back({x,z});
    }

    dfs(1,0);

    cout<<dp[1][k]<<'\n';

    return 0 ^ _ ^ 0;
}

重建道路

设 $dp[x][i]$ 表示在以 $x$ 为根的子树内，获得大小为 $i$ 的子树所需要删除的边的个数。

当我们想获得大小为 1 的子树时只需要将儿子节点的连边删掉即可，于是可以初始化

$$
dp[x][1]=
\left{
\begin{aligned}
&g[x].size(),x为根\
&g[x].size()-1,x不为根\
\end{aligned}
\right.$$

$g[x].size()$ 表示点 $x$ 的度数，注意在根处需要特判。

因为在初始化的时候就已经将儿子节点的连边删掉了，所以当子节点向父节点转移时，若选择与父节点相连，需要将这条删掉的边加回来，或者说是将删除的边的个数减一，于是可以得到以下状态转移方程

$$dp[x][i+j]=min(dp[x][i+j],dp[x][i]+dp[to][j]-1)$$

注意每棵子树更新完后都要更新一次全局答案，更新时注意子树必须要与父节点断开。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int maxn=5050,mod=998244353,INF=1e9;
vector<int> g[maxn];
int dp[maxn][maxn];
int siz[maxn];
int ans;
int m;

void dfs(int x,int fa){
    dp[x][0]=0;
    if(x==1)dp[x][1]=g[x].size();
    else dp[x][1]=g[x].size()-1;
    siz[x]=1;
    for(int to:g[x]){
        if(to==fa)continue;
        dfs(to,x);
        for(int i=siz[x];i>=1;i--){
            for(int j=1;j<=siz[to];j++){
                dp[x][i+j]=min(dp[x][i+j],dp[x][i]+dp[to][j]-1);
            }
        }
        siz[x]+=siz[to];
    }
    if(x==1)ans=min(ans,dp[x][m]);
    else ans=min(ans,dp[x][m]+1);
}

void solve(){
    int n;
    cin>>n>>m;

    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            dp[i][j]=INF;
        }
    }

    ans=INF;

    dfs(1,0);
    cout<<ans<<'\n';
}

signed main(){
    ios::sync_with_stdio(0);
    int t=1;
    // cin>>t;
    while(t--){
        solve();
    }

    return 0;
}

Components

依然是树上背包，考虑从儿子向父亲转移时是否能够形成一个连通块，那么我们必须知道儿子节点是否被选在某个连通块中，于是我们可以设 $dp[u][i][0/1]$ 表示以 $x$ 为根的子树，子树里面总共选 $i$ 个连通块，$x$ 自己选不选，的方案数有多少。我们可以分三种情况讨论。

若 $x$ 不选， $to$ 选不选都行，就有

$$dp[x][i+j][0]+=dp[x][i][0]*(dp[to][j][0]+dp[to][j][1])$$

若 $x$ 选， $to$ 不选，就有

$$dp[x][i+j][1]+=dp[x][i][1]*dp[to][j][0]$$

若 $x$ 选， $to$ 也选，两者会形成一个连通块，使得总连通块个数减一，就有

$$dp[x][i+j-1][1]+=dp[x][i][1]*dp[to][j][1]$$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int maxn=5050,mod=998244353,INF=1e9;
vector<int> g[maxn];
int dp[maxn][maxn][2];
int siz[maxn];
int n;

void dfs(int x,int fa){
    dp[x][0][0]=dp[x][1][1]=1;
    siz[x]=1;
    for(int to:g[x]){
        if(to==fa)continue;
        dfs(to,x);
        for(int i=siz[x];i>=0;i--){
            for(int j=siz[to];j>=1;j--){
                (dp[x][i+j][0]+=dp[x][i][0]*(dp[to][j][0]+dp[to][j][1])%mod)%=mod;
                if(i==0)continue;
                (dp[x][i+j][1]+=dp[x][i][1]*dp[to][j][0]%mod)%=mod;
                (dp[x][i+j-1][1]+=dp[x][i][1]*dp[to][j][1]%mod)%=mod;
            }
        }
        siz[x]+=siz[to];
    }
}

void solve(){
    cin>>n;

    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    dfs(1,0);

    for(int i=1;i<=n;i++){
        cout<<(dp[1][i][1]+dp[1][i][0])%mod<<'\n';
    }
}

signed main(){
    ios::sync_with_stdio(0);
    int t=1;
    // cin>>t;
    while(t--){
        solve();
    }

    return 0;
}

Tree Patrolling

一点节点会出现三种情况：不被守卫，没人但被守卫，有人。并且这三种情况都会影响我们 dp 的转移，所以在设计 dp 状态时就需要将他们考虑进去。

于是我们可以设 $dp[x][i][3]$ 表示在以 $x$ 为根的子树内，有 $i$ 个节点被守卫，$x$ 自己不被守卫或没人但被守卫或有人的方案数。分三种情况讨论。

若 $x$ 不被守卫，那么 $to$ 没有人就行。

$$dp[x][i+j][0]+=dp[x][i][0]*(dp[to][j][0]+dp[to][j][1])$$

若 $x$ 没人但被守卫，此时又有两种情况：第一种是此前 $x$ 尚未被守卫，直到 $to$ 有人后 $x$ 才被守卫；第二种是此前 $x$ 已经被守卫，注意此时被守卫的节点数多一。

$$dp[x][i+j][1]+=dp[x][i][1]*(dp[to][j][0]+dp[to][j][1]+dp[to][j][2])$$

$$dp[x][i+j+1][1]+=dp[x][i][0]*dp[to][j][2]$$

若 $x$ 有人， $to$ 没有限制，但要注意 $to$ 不被守卫时总的被守卫的节点数多一。

$$dp[x][i+j][2]+=dp[x][i][2]*(dp[to][j][1]+dp[to][j][2])$$

$$dp[x][i+j+1][2]+=dp[x][i][2]*dp[to][j][0]$$

转移时需要暂存答案避免转移过程中被覆盖。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int maxn=2050,mod=1e9+7,INF=1e9;
vector<int> g[maxn];
int dp[maxn][maxn][3],ndp[maxn][3]; //0:不被守卫 1:没人但被守卫 2:有人
int siz[maxn];
int ans;

void dfs(int x,int fa){
    dp[x][0][0]=dp[x][1][2]=1;
    siz[x]=1;
    for(int to:g[x]){
        if(to==fa)continue;
        dfs(to,x);
        for(int i=0;i<=siz[x];i++){
            ndp[i][0]=dp[x][i][0];
            ndp[i][1]=dp[x][i][1];
            ndp[i][2]=dp[x][i][2];
            dp[x][i][0]=dp[x][i][1]=dp[x][i][2]=0;
        }
        for(int i=siz[x];i>=0;i--){
            for(int j=siz[to];j>=0;j--){
                (dp[x][i+j][0]+=ndp[i][0]*(dp[to][j][0]+dp[to][j][1])%mod)%=mod;

                (dp[x][i+j][1]+=ndp[i][1]*(dp[to][j][0]+dp[to][j][1]+dp[to][j][2])%mod)%=mod;
                (dp[x][i+j+1][1]+=ndp[i][0]*dp[to][j][2]%mod)%=mod;

                (dp[x][i+j][2]+=ndp[i][2]*(dp[to][j][1]+dp[to][j][2])%mod)%=mod;
                (dp[x][i+j+1][2]+=ndp[i][2]*dp[to][j][0]%mod)%=mod;
            }
        }
        siz[x]+=siz[to];
    }
}

void solve(){
    int n;
    cin>>n;

    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    ans=INF;

    dfs(1,0);
    for(int i=0;i<=n;i++){
        int ans=0;
        for(int k=0;k<=2;k++){
            (ans+=dp[1][i][k])%=mod;
        }
        cout<<ans<<'\n';
    }
}

signed main(){
    ios::sync_with_stdio(0);
    int t=1;
    // cin>>t;
    while(t--){
        solve();
    }

    return 0;
}

Karen and Supermarket

设 $dp[x][i][0/1]$ 表示在以 $x$ 为根的子树内，$x$ 用或者不用优惠券时，选 $i$ 件物品需要的最小代价。

不难发现，当所在节点想要使用优惠券时，那么其父节点必须使用优惠券，于是可以得到状态转移方程：

$$dp[x][i+j][0]=min(dp[x][i+j][0],dp[x][i][0]+dp[to][j][0])$$

$$dp[x][i+j][1]=min(dp[x][i+j][1],dp[x][i][1]+dp[to][j][0])$$

$$dp[x][i+j][1]=min(dp[x][i+j][1],dp[x][i][1]+dp[to][j][1])$$

最后判断一下花费是否超过 $b$ 元，取其中购买商品最多的即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int maxn=5050,mod=1e9+7,INF=1e18;
vector<int> g[maxn];
int c[maxn],d[maxn];
int dp[maxn][maxn][2]; // i 子树内选 j 件物品，根是否使用优惠的最小代价
int siz[maxn];
int n,k;

void dfs(int x,int fa){
    dp[x][0][0]=0;
    dp[x][1][0]=c[x];
    dp[x][1][1]=c[x]-d[x];
    siz[x]=1;
    for(int to:g[x]){
        dfs(to,x);
        for(int i=siz[x];i>=0;i--){
            for(int j=siz[to];j>=0;j--){
                dp[x][i+j][0]=min(dp[x][i+j][0],dp[x][i][0]+dp[to][j][0]);
                dp[x][i+j][1]=min(dp[x][i+j][1],dp[x][i][1]+dp[to][j][0]);
                dp[x][i+j][1]=min(dp[x][i+j][1],dp[x][i][1]+dp[to][j][1]);
            }
        }
        siz[x]+=siz[to];
    }
}

void solve(){
    cin>>n>>k;

    cin>>c[1]>>d[1];

    for(int i=2;i<=n;i++){
        int x;
        cin>>c[i]>>d[i]>>x;
        g[x].push_back(i);
    }

    for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++){
            dp[i][j][0]=dp[i][j][1]=INF;
        }
    }

    dfs(1,0);

    int ans=0;
    for(int i=n;i>=0;i--){
        if(min(dp[1][i][0],dp[1][i][1])<=k){
            ans=i;
            break;
        }
    }
    cout<<ans<<'\n';
}

signed main(){
    ios::sync_with_stdio(0);
    int t=1;
    // cin>>t;
    while(t--){
        solve();
    }

    return 0;
}

Paint Tree 2

要求涂树上最多 $k$ 条互不相交链，最大化链上节点的权值和。可以发现节点要么不在链上，要么在链的端点，要么在链的中间，于是可以设 $dp[x][i][0/1/2]$，表示在以 $x$ 为根的子树内，$x$ 不在链上或在链的端点或在链的中间，选 $i$ 链的最大价值和。

令 $mx=max{dp[to][j][0],dp[to][j][1],dp[to][j][2]}$。

若 $x$ 不在链上，那么 $to$ 没有限制，取最大价值即可。

$$dp[x][i+j][0]=max(dp[x][i+j][0],dp[x][i][0]+mx)$$

若 $x$ 在链的端点，此时有两种情况：第一种是 $x$ 原来就在链的端点， $to$ 没有限制；第二种是 $x$ 原来不在链上， $to$ 在链的端点，此时两者可以相连。

$$dp[x][i+j][1]=max(dp[x][i+j][1],dp[x][i][1]+mx)$$
$$dp[x][i+j][1]=max(dp[x][i+j][1],dp[x][i][0]+dp[to][j][1]+a[x])$$

若 $x$ 在链的中间，此时有两种情况：第一种是 $x$ 原来就在链的中间， $to$ 没有限制；第二种是 $x$ 原来在链的端点， $to$ 也在链的端点，此时两者可以相连，链数减一。

$$dp[x][i+j][2]=max(dp[x][i+j][2],dp[x][i][2]+mx)$$
$$dp[x][i+j-1][2]=max(dp[x][i+j-1][2],dp[x][i][1]+dp[to][j][1])$$

转移时需要暂存答案避免转移过程中被覆盖。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int maxn=200050,mod=1e9+7,INF=1e18;
vector<int> g[maxn];
int a[maxn];
int dp[maxn][10][3],ndp[10][3]; //0:没选  1:链的端点  2:链的中间
int n,k;

void dfs(int x,int fa){
    dp[x][0][0]=0;
    dp[x][1][1]=dp[x][1][2]=a[x];
    for(int to:g[x]){
        if(to==fa)continue;
        dfs(to,x);
        for(int i=0;i<=k;i++){
            ndp[i][0]=ndp[i][1]=ndp[i][2]=-INF;
        }
        for(int i=0;i<=k;i++){
            for(int j=0;j<=k;j++){
                if(i+j-1>k)continue;
                int mx=max(dp[to][j][0],max(dp[to][j][1],dp[to][j][2]));
                ndp[i+j][0]=max(ndp[i+j][0],dp[x][i][0]+mx);

                ndp[i+j][1]=max(ndp[i+j][1],dp[x][i][1]+mx);
                ndp[i+j][1]=max(ndp[i+j][1],dp[x][i][0]+dp[to][j][1]+a[x]);

                ndp[i+j][2]=max(ndp[i+j][2],dp[x][i][2]+mx);
                if(i+j>=1)ndp[i+j-1][2]=max(ndp[i+j-1][2],dp[x][i][1]+dp[to][j][1]);
            }
        }
        for(int i=0;i<=k;i++){
            dp[x][i][0]=ndp[i][0];
            dp[x][i][1]=ndp[i][1];
            dp[x][i][2]=ndp[i][2];
        }
    }
}

void solve(){
    cin>>n>>k;

    for(int i=1;i<=n;i++){
        cin>>a[i];
    }

    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    for(int i=1;i<=n;i++){
        for(int j=0;j<=k;j++){
            dp[i][j][0]=dp[i][j][1]=dp[i][j][2]=-INF;
        }
    }
    dfs(1,0);

    int ans=0;
    for(int i=0;i<=k;i++){
        ans=max(ans,max(dp[1][i][0],max(dp[1][i][1],dp[1][i][2])));
    }
    cout<<ans<<'\n';
}

signed main(){
    ios::sync_with_stdio(0);
    int t=1;
    // cin>>t;
    while(t--){
        solve();
    }

    return 0;
}

潜入行动

设 $dp[x][i][0/1][0/1]$ 表示在以 $x$ 为根的子树内，放了 $i$ 个监听设备，$x$ 节点有无设备，$x$ 节点是否被监听的方案数。需要讨论以下四种情况。

若 $x$ 没放设备且没被监听，那么 $to$ 一定不能放设备并且一定被监听。

$$dp[x][i+j][0][0]+=dp[x][i][0][0]*dp[to][j][0][1]$$

若 $x$ 放了设备但没被监听，那么 $to$ 一定不能放设备，是否被监听无所谓。

$$dp[x][i+j][1][0]+=dp[x][i][1][0]*(dp[to][j][0][0]+dp[to][j][0][1])$$

若 $x$ 没放设备但被监听，此时有两种情况：第一种是 $x$ 原来就没放设备但被监听，那么只需 $to$ 被监听；第二种是 $x$ 原来没放设备且没被监听，那么 $to$ 一定要放了设备且被监听。

$$dp[x][i+j][0][1]+=dp[x][i][0][1](dp[to][j][0][1]+dp[to][j][1][1])$$
$$dp[x][i+j][0][1]+=dp[x][i][0][0]dp[to][j][1][1]$$

若 $x$ 放了设备且被监听，此时有两种情况：第一种是 $x$ 原来就放了设备且被监听，那么 $to$ 没有限制；第二种是 $x$ 原来放了设备但没被监听，那么 $to$ 放了设备就行。

$$dp[x][i+j][1][1]+=dp[x][i][1][1]*(dp[to][j][0][0]+dp[to][j][1][0]+dp[to][j][0][1]+dp[to][j][1][1])$$

$$dp[x][i+j][1][1]+=dp[x][i][1][0]*(dp[to][j][1][0]+dp[to][j][1][1])$$

转移时需要暂存答案避免转移过程中被覆盖。dp 数组开 long long 会 MLE，所以只能在运算过程中转为 long long 计算。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100050, mod = 1e9 + 7, INF = 1e9;
vector<int> g[maxn];
int dp[maxn][105][2][2], ndp[105][2][2]; //有无设备，是否被监听
int siz[maxn];
int n, k;

void dfs(int x, int fa) {
    dp[x][0][0][0] = dp[x][1][1][0] = 1;
    siz[x] = 1;
    for (int to : g[x]) {
        if (to == fa)continue;
        dfs(to, x);
        for (int i = 0;i <= min(k, siz[x]);i++) {
            ndp[i][0][0] = dp[x][i][0][0];
            ndp[i][1][0] = dp[x][i][1][0];
            ndp[i][0][1] = dp[x][i][0][1];
            ndp[i][1][1] = dp[x][i][1][1];
            dp[x][i][0][0] = dp[x][i][1][0] = dp[x][i][0][1] = dp[x][i][1][1] = 0;
        }

        for (int i = 0;i <= min(k, siz[x]);i++) {
            for (int j = 0;j <= min(k, siz[to]);j++) {
                if(i+j>k)continue;
                (dp[x][i+j][0][0]=1ll*dp[x][i+j][0][0]+1ll*ndp[i][0][0]*dp[to][j][0][1]%mod) %= mod;

                (dp[x][i+j][1][0]=1ll*dp[x][i+j][1][0]+1ll*ndp[i][1][0]*(1ll*dp[to][j][0][0]+dp[to][j][0][1])%mod) %= mod;

                (dp[x][i+j][0][1]=1ll*dp[x][i+j][0][1]+1ll*ndp[i][0][1]*(1ll*dp[to][j][0][1]+dp[to][j][1][1])%mod) %= mod;
                (dp[x][i+j][0][1]=1ll*dp[x][i+j][0][1]+1ll*ndp[i][0][0]*dp[to][j][1][1]%mod) %= mod;

                (dp[x][i+j][1][1]=1ll*dp[x][i+j][1][1]+1ll*ndp[i][1][1]*(1ll*dp[to][j][0][0]+dp[to][j][1][0]+dp[to][j][0][1]+dp[to][j][1][1])%mod) %= mod;
                (dp[x][i+j][1][1]=1ll*dp[x][i+j][1][1]+1ll*ndp[i][1][0]*(1ll*dp[to][j][1][0]+dp[to][j][1][1])%mod) %= mod;
            }
        }
        siz[x] += siz[to];
    }
}

void solve() {
    cin >> n >> k;

    for (int i = 1;i < n;i++) {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    dfs(1, 0);

    cout << (1ll*dp[1][k][0][1]+dp[1][k][1][1])%mod << '\n';
}

signed main() {
    ios::sync_with_stdio(0);
    int t = 1;
    // cin>>t;
    while (t--) {
        solve();
    }

    return 0;
}

总结

  • 主要思路是从子节点向父节点转移，讨论可能出现的情况，枚举子树中物品的分配，获得当前子树的价值
  • 注意 dp 数组的初始化是对当前子树考虑
  • 注意控制好枚举的方向和上下界
  • 注意转移时是否会被覆盖
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																				
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

					

						




    

         备案号 
        
            桂ICP备2025064077号
        
    

    

         Copyright 
        2020-2025
            西瓜nd
        
        
    


						
Theme Argon By solstice23