P2465山贼集团

独秀平川 · 2018-05-28 21:08:13 · 题解

其实不用多叉树转二叉树，只需要跑一遍正常的树上背包就行了。树上背包的模板，详见P1273有线电视网。

我们先预处理出val[ ]数组，val[i]代表一个节点同时被且仅被i的二进制数中是1的位的分部占领得到的收益，如i=11，二进制为1011，表示被1,2,4号分部占领的收益。

dp[i][j]为第i号村庄的子树（包括i村），内部有j状态的分部（状态的意义同val）的最大价值，初始状态为j状态的分部都建立在i村的代价。

dp[i][j]=所有以i的儿子为根的子树，包含分部状态一共为j的最大值+i号村庄对答案的贡献（即val[j]，子树中所有村庄都占领了i村）。

#include <iostream>
#include <algorithm>
#include <string.h>
#include <stdio.h>
#include <math.h>
using namespace std;
typedef long long LL;
const int MAX=110;
struct edge
{
    int to,nxt;
}e[MAX*2];
int head[MAX],tot;
int n,m;
int val[4100];//4100是状态数
void addedge(int fr,int to)
{
    e[++tot].to=to;
    e[tot].nxt=head[fr];
    head[fr]=tot;
}
void addtwo(int fr,int to){addedge(fr,to);addedge(to,fr);}
int dp[MAX][4100];
void initdp()
{
    int cost[MAX][13];
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<m;j++)
        {
            scanf("%d",&cost[i][j]);
        }
        dp[i][0]=0;
        for(int j=1;j<(1<<m);j++)
        {
            int lowbit=j&(-j);
            int lowid=(log(lowbit)+0.001)/log(2);
            dp[i][j]=dp[i][j^lowbit]-cost[i][lowid];//初始化dp
        }
    }
}
void calval(int x)
{
    for(int i=1;i<=x;i++)
    {
        int v,cnt,s=0;
        scanf("%d%d",&v,&cnt);
        for(int j=1;j<=cnt;j++)//输入互相影响的村庄
        {
            int mem;
            scanf("%d",&mem);
            s|=(1<<(mem-1));//状压存储
        }
        //所有包含s的集合的val都被影响
        int maxm=(1<<m)-1;val[s]+=v;
        int tmp=s^maxm;
        for(int j=tmp;j;j=(j-1)&tmp)//枚举子集的好方法
        {
            val[(s|j)]+=v;
        }
    }
}
void dfs(int now,int fa)
{
    for(int i=head[now];i!=-1;i=e[i].nxt)//枚举儿子
    {
        int son=e[i].to;
        if(son!=fa)
        {
            dfs(son,now);
            for(int j=(1<<m)-1;j;j--)
            {
                for(int k=j;k;k=(k-1)&j)
                {
                    dp[now][j]=max(dp[now][j],dp[now][j^k]+dp[son][k]);
                    //dp[now][j]：不选此子树，dp[now][j^k]+dp[son][k]：选此子树
                }
            }
        }
    }
    for(int i=(1<<m)-1;i;i--)
    {
        dp[now][i]+=val[i];//加now的贡献
    }
}
void init()
{
    memset(head,-1,sizeof(head));tot=-1;
    memset(val,0,sizeof(val));
}
int main()
{
    cin>>n>>m;
    init();
    for(int i=1;i<n;i++)
    {
        int fr,to;
        scanf("%d%d",&fr,&to);
        addtwo(fr,to);
    }
    initdp();
    int t;scanf("%d",&t);
    calval(t);
    dfs(1,0);
    cout<<dp[1][(1<<m)-1]<<endl;
    return 0;
}