HDU 6268 Master of Subgraph （2017CCPC杭州 E）分治+bitset优化

题目传送门

题意：给你一颗n(<=3e3)个点的无向树，再给你一个数m(<=1e5)，再给你n个点的权值a[i](<=1e5)

求对于每个x属于[1,m]，是否存在一个连通子图的权值和正好为x。输出一个长度为m的01串，第i个位置上的数字表示是否存在连通子图的权值和正好为i。

思路：点分治+bitset优化

知识盲区。。。打重现的时候满脑子暴力优化，然后T到结束。。。

考虑枚举每个点，找出包含这个点的所有连通子图的权值（这里需要注意，枚举节点u为根时，往下搜索的每一步都是要包含其父节点的答案状态，用bitset存，第i位为1表示存在经过u的连通子图的权值和正好为i）。

这样直接搜是O(n^2)的，再乘上m(?)可能要爆炸。

考虑用分治优化到nlogn。

每次寻找树的重心，并枚举重心往下搜索。

注意初始化。

代码：

#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define mst(head,x,n) memset(head+1,x,n*sizeof(head[0]))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dep(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int maxn=3e3+5;
const int maxm=2e5+5;
//const double pi=acos(-1.0);
//const double eps=1e-9;
//const ll mo=1e9+7;
int n,m,k;
int a[maxn],c[maxn];
int tmp,cnt,rt;
int flag;
int sz[maxn];
bool ok[maxn];
vector<int>vc[maxn];
bitset<100010>ans,zt[maxn];
template <typename T>
inline void read(T &X){
    X=0;int w=0; char ch=0;
    while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
    while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    if(w) X=-X;
}
void dfs(int u,int fa,int n){
    sz[u]=1;c[u]=0;
    for(int i=0;i<vc[u].size();i++){
        int v=vc[u][i];
        if(v==fa||ok[v]) continue;
        dfs(v,u,n);
        sz[u]+=sz[v];
        c[u]=max(c[u],sz[v]);
    }
    c[u]=max(c[u],n-c[u]);
    if(c[u]<c[rt]) rt=u;
}
void getdp(int u,int fa){
    sz[u]=1;
    zt[u]<<=a[u];
    for(int i=0;i<vc[u].size();i++){
        int v=vc[u][i];
        if(v==fa||ok[v]) continue;
        zt[v]=zt[u];
        getdp(v,u);
        zt[u]|=zt[v];
        sz[u]+=sz[v];
    }
}
void solve(int u){
    zt[u].reset();zt[u][0]=1;
    ok[u]=true;
    getdp(u,-1);
    ans|=zt[u];
    for(int i=0;i<vc[u].size();i++){
        int v=vc[u][i];
        if(ok[v]) continue;
        rt=0;
        dfs(v,-1,sz[v]);
        solve(rt);
    }
}
int main(){

#ifdef ONLINE_JUDGE
#else
    freopen("D:/Temp/in.txt", "r", stdin);
#endif

    int T,cas=1;
    read(T);
    while(T--)
    {
        read(n);read(m);
        ans.reset();
        rep(i,1,n) {vc[i].clear();ok[i]=false;}
        rep(i,1,n-1){
            int u,v;
            read(u);read(v);
            vc[u].push_back(v);
            vc[v].push_back(u);
        }
        rep(i,1,n) read(a[i]);
        rt=0;c[rt]=inf;
        dfs(1,-1,n);
        //cout<<"&^%"<<rt<<endl;
        solve(rt);
        rep(i,1,m)
        printf("%d",(int)ans[i]);
        puts("");
    }
    return 0;
}