题解：P2465 [SDOI2008] 山贼集团

chaeminter2467 · 2025-10-16 15:17:42 · 题解

P2465 [SDOI2008] 山贼集团

模拟赛的 T0。

题解

观察 P 的范围，发现可以状压，往这方面考虑。发现对于一个节点 u，管控其的分部即为 u 子树内的分部。

设 dp_{u,S} 表示节点 u，其子树内的分部集合为 S 的最大收益。那么有初始化就是 dp_{u,S} = \sum_{x \in S} a_{u,x}，也就是直接在 u 修建 S 内的所有分部。

合并子节点和父亲节点的过程形如树上背包，也就是 dp_{u,S \cup T} = \max(dp_{v,T},dp_{u,S})。

直接做转移就可以了。注意还要加上分部合作带来的价值，记 g_{S} 为一个节点的子树内有分部 S 带来的贡献，g_{S} 的计算也比较简单，为 g_{S} = \sum_{T \subset S} val_{T}。

枚举子集时间复杂度为 3^P，总时间复杂度为 O(N 3^P)。

code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define il inline
#define lb(x) ((x)&(-(x)))
const int N=102,maxp=13;
const ll lnf=-(1e15+38);
int n,m,rep,sta;
ll a[1<<maxp],dp[N][1<<maxp];
ll dvt[1<<maxp];
namespace Graph{
    int hd[N],cnt=0;
    struct edge{int to,nxt;}e[N<<1];
    void ade(int from,int to){e[++cnt]={to,hd[from]};hd[from]=cnt;}
}using namespace Graph;
il void gmx(ll &x,ll y){x=max(x,y);}
void dfs(int u,int fa){
    for(int i=hd[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa) continue;
        dfs(v,u);
        for(int s=sta;s;s--) for(int t=s;t;t=(t-1)&s) gmx(dp[u][s],dp[u][s^t]+dp[v][t]);//树上背包
    }
    for(int s=1;s<=sta;s++) dp[u][s]+=dvt[s];//加上分部合作的贡献

}
int main(){
    cin>>n>>rep;sta=(1<<rep)-1;
    for(int i=1,u,v;i<n;i++){
        cin>>u>>v;
        ade(u,v);ade(v,u);
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<rep;j++) cin>>a[1<<j];
        for(int s=1;s<=sta;s++) for(int t=s;t;t^=lb(t)) dp[i][s]-=a[lb(t)];//初始化dp数组
    }
    cin>>m;
    for(int val,num,x,s;m;m--){
        cin>>val>>num;s=0;
        for(;num;num--){
            cin>>x;
            s|=(1<<(x-1));
        }
        dvt[s]+=val;//即上文中的g数组
    }
    for(int s=sta;s;s--) for(int t=s&(s-1);t;t=(t-1)&s) dvt[s]+=dvt[t];//注意s要从大到小枚举，因为正着更新会导致某些值被重复计算，可以利用树上背包的思想
    dfs(1,0);
    cout<<dp[1][sta]<<'\n';
    return 0;
}