洛谷2465 [SDOI2008]山贼集团

题意

在树上放一些山贼集团的分部，每个分部可以收取根节点到它路径上所有节点的保护费。在节点 $i$ 建立分部 $j$ 花费 $s[i][j]$ 。对于每一个节点，如果它被多个分部收保护费，就可能产生收益或损失。

求最优的放置方法，可以得到最大利润。

其中点数 $N\le 100$ ，分部个数 $P\le 12$ 。

题解

看到 $P$ 的范围，显然可以对节点上放置分部的状态进行状压。因为每个分部收取的保护费都与根节点有关，所以是树形dp。

用 $f[x][i]$ 表示以 $x$ 为根的子树，子树中所有节点放置分部的状态为 $i$ 时的最优解。每次转移时枚举当前状态的子集给子节点即可，方程式为：

$$f[x][i]=max(f[x][i],f[y][j]+f[x][i \ xor \ j]) \ , \ j\in i$$

$f[x][i]$ 的初值是在 $x$ 上建立状态 $i$ 里的所有节点的花费（负数）。看起来似乎不太对，但仔细一想其实没有问题。叶节点的初值赋为这个显然没有问题，而非叶节点都是从叶节点转移。

还需要预处理一个节点被多个分部收保护费时的收益或损失情况。注意所有包含这个状态的子集都需要被计算。

还有因为是类似背包的做法，所以要倒序枚举。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

struct Edge {
    int next,to;
} edge[205];
int cnt,head[105],n,m,a,b,c,p,t,s[105][15],v[4096],f[105][4096];

inline void add(int u,int v)
{
    edge[++cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

void dfs(int x,int fa)
{
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to;
        if (y==fa) continue;
        dfs(y,x);
        for (int j=m-1;j>=0;j--)
            for (int k=j;k;k=(k-1)&j)
                f[x][j]=max(f[x][j],f[y][k]+f[x][j^k]);
    }
    for (int i=0;i<m;i++) f[x][i]+=v[i];
}

int main()
{
    n=read(); p=read();
    m=1<<p;
    for (int i=1;i<n;i++)
    {
        a=read(); b=read();
        add(a,b);
        add(b,a);
    }
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=p;j++) s[i][j]=read();
        for (int j=0;j<m;j++)
        {
            for (int k=1;k<=p;k++)
            {
                if (!(j&(1<<(k-1)))) continue;
                f[i][j]-=s[i][k];
            }
        }
    }
    t=read();
    for (int i=1;i<=t;i++)
    {
        b=read(); c=read();
        int now=0;
        for (int j=1;j<=c;j++) now|=(1<<(read()-1));
        v[now]+=b;
        int now2=now^(m-1);
        for (int j=now2;j;j=(j-1)&now2) v[now|j]+=b;
    }
    dfs(1,0);
    return !printf("%d",f[1][m-1]);
}