题解：P2465 [SDOI2008] 山贼集团

· · 题解

注意到 p \leq 12 非常小，考虑状压。设 f_{u, s} 为 u 子树内建立了 s 中的分部的最大答案。转移首先考虑合并子树，有

f'_{u, s \cup t} \gets f_{u, s} + f_{v, t}

直接枚举是 \mathcal{O}(4^p) 的，显然不行，注意到 s, t 必然无交，所以可以枚举 x = s \cup t，枚举 s 为 x 的子集，就有 t = x \setminus s，即

f'_{u, x} \gets f_{u, s} + f_{v, x \setminus s}

将复杂度降到了枚举子集的 \mathcal{O}(3^p)。

合并子树后仅需讨论 u 上建立的分部并加上 u 点的贡献，转移都是简单的。总时间复杂度 \mathcal{O}(n3^p)。

Code：

#include<bits/stdc++.h>
#define mem(a, v) memset(a, v, sizeof(a))

using namespace std;

const int maxn = 100 + 10, maxk = 12;

struct{
    int v, nex;
} edge[maxn << 1];

int n, k, m;
int a[maxn][maxk + 10], b[1 << maxk], f[maxn][1 << maxk], g[1 << maxk];
int head[maxn], top = 0;

inline void add(int u, int v, bool o = true){
    edge[++top].v = v, edge[top].nex = head[u], head[u] = top, o && (add(v, u, false), 1538);
}

inline void dfs(int u, int fa){
    mem(f[u], -0x3f), f[u][0] = 0;
    for (int i = head[u]; i; i = edge[i].nex){
        const int v = edge[i].v;
        if (v != fa){
            dfs(v, u), mem(g, -0x3f);
            for (int sta = 0; sta < 1 << k; sta++){
                for (int st = sta;;st = st - 1 & sta){
                    g[sta] = max(g[sta], f[u][st] + f[v][sta ^ st]);
                    if (!st){
                        break;
                    }
                }
            }
            for (int sta = 0; sta < 1 << k; sta++){
                f[u][sta] = g[sta];
            }
        }
    }
    for (int i = 1; i <= k; i++){
        for (int sta = 0; sta < 1 << k; sta++){
            (sta >> i - 1 & 1) && (f[u][sta] = max(f[u][sta], f[u][sta ^ 1 << i - 1] - a[u][i]));
        }
    }
    for (int sta = 0; sta < 1 << k; sta++){
        for (int st = sta;;st = st - 1 & sta){
            f[u][sta] += b[st];
            if (!st){
                break;
            }
        }
    }
}

int main(){
    scanf("%d %d", &n, &k);
    for (int i = 1; i < n; i++){
        int u, v;
        scanf("%d %d", &u, &v), add(u, v);
    }
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= k; j++){
            scanf("%d", &a[i][j]);
        }
    }
    scanf("%d", &m);
    for (int i = 1; i <= m; i++){
        int v, k, x = 0;
        scanf("%d %d", &v, &k);
        for (int u; k--; scanf("%d", &u), x |= 1 << u - 1);
        b[x] += v;
    }
    dfs(1, 0);
    printf("%d\n", f[1][(1 << k) - 1]);

return 0;
}