本文共 2571 字，大约阅读时间需要 8 分钟。

题意：给定一棵 n 个点的树，每个点有一个权值 w[i]，现在我们可以选一些连通的点，并且把这点选出来的点的权值相加，得到一个和。求 [1, m] 里面哪些值可以被表示成选出来的点的权值和。用0101序列的方式输出。

思路：

考虑点分治。先选出树的重心，考虑一定要选这个点的答案。假设我选择了某个点，那么我必须选择这个点的父亲。现在开始递归这棵树。每次递归到一个点，这个点的bitset初值化为父亲结点表示的bitset右移w[x]位。他的意义是，当前这个点如果选了，那么他的父亲必选，那也就是求他父亲当前求得的答案集合结合这个点的权值的答案。回溯的时候，父亲表示的bitset要或上儿子表示的bitset。这是因为在后面这个父亲的其他儿子求解的之后，要用到这个父亲已经求得的信息，并结合起来，通过这个父亲起到连接的效果。

最后以当前这个分治中心为根的树的答案就是分治中心表示的bitset，那么接下来继续往下递归求解就可以了。

时间复杂度O(nlogn⋅mw)

#include
   
    using namespace std;typedef long long ll;const int mod = 998244353;const double eps = 1e-11;const int N = 3e3 + 10;const int M = 1e5 + 10;inline int read() {    int x = 0, f = 1; char ch = getchar();    while(!isdigit(ch)) {        if(ch == '-') f = -1;        ch = getchar();    }    while(isdigit(ch))        x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();    return x * f;}///all表示当前子树的结点数int n, all, sz[N], rt, rt2, a[N], siz[N], maxson[N], maxx;vector
    
     mp[N];bitset
     
      bit[N], ans;bool vis[N];void init() {    ans.reset();    for(int i = 1; i <= n; ++i) vis[i] = 0;    for(int i = 1; i <= n; ++i) mp[i].clear();}void getrt(int u, int fa) {    siz[u] = 1;    maxson[u] = 0;    int sz = mp[u].size();    for(int i = 0; i < sz; ++i) {        int v = mp[u][i];        if(v == fa || vis[v]) continue;        getrt(v, u);        siz[u] = siz[u] + siz[v];        maxson[u] = max(maxson[u], siz[v]);    }    maxson[u] = max(maxson[u], all - siz[u]);    if((maxson[u] << 1) <= all) rt2 = rt, rt = u;}void calc(int u, int fa) {    siz[u] = 1, bit[u] <<= a[u];    int sz = mp[u].size();    for(int i = 0; i < sz; ++i) {        int v = mp[u][i];        if(vis[v] || v == fa) continue;        bit[v] = bit[u];        calc(v, u);        siz[u] += siz[v];        bit[u] |= bit[v];    }}void divide(int u) {    vis[u] = 1;    bit[u].reset(), bit[u].set(0);    calc(u, 0);    ans |= bit[u];    int sz = mp[u].size();    for(int i = 0; i < sz; ++i) {        int v = mp[u][i];        if(vis[v]) continue;        rt = rt2 = 0;        maxson[rt] = all = siz[v];        getrt(v, 0);        divide(rt);    }}int main() {    int t, m, u, v;    t = read();    while(t--) {        n = read(), m = read();        init();        for(int i = 1; i < n; ++i) {            u = read(), v = read();            mp[u].push_back(v);            mp[v].push_back(u);        }        for(int i = 1; i <= n; ++i) a[i] = read();        rt = rt2 = 0;        maxson[rt] = all = n;        getrt(1, 0);        getrt(rt, 0);        divide(rt);        for(int i = 1; i <= m; ++i) printf("%d", (int)ans[i]);        printf("\n");    }    return 0;}
     
    
   

转载地址：http://wcio.baihongyu.com/