CCPC 2016 杭州 E. Master of Subgraph（点分治+bitset优化DP）

题目链接：http://acm.hdu.edu.cn/downloads/CCPC2018-Hangzhou-ProblemSet.pdf

题意：给定一棵有 n 个结点的树和一个数 m，对于 i ∈ [1，m] 问是否存在一个子图结点的权值和为 i 。

题解：一个显然的思路是树上做背包，但显然会 T。要遍历全部子图，考虑进行点分治，然后合并的时候用 bitset 优化背包，时间复杂度O(nmlogn / 64)，且时限给了 8s。

 #include <bits/stdc++.h>

 using namespace std;

 #define ll long long

 #define ull unsigned long long

 #define mst(a,b) memset((a),(b),sizeof(a))

 #define mp(a,b) make_pair(a,b)

 #define pi acos(-1)

 #define pii pair<int,int>

 #define pb push_back

 const int INF = 0x3f3f3f3f;

 const double eps = 1e-;

 const int maxn = 3e3 + ;

 const int maxm = 1e5 + ;

 const ll mod =  ;

 int n,m;

 vector<int>vec[maxn];

 bool used[maxn];

 int a[maxn],root,sz[maxn],son[maxn],all;

 void getroot(int u,int fa) {

     sz[u] = , son[u] = ;

     for(int i = ; i < vec[u].size(); i++) {

         int v = vec[u][i];

         if(used[v] || v == fa) continue;

         getroot(v,u);

         sz[u] += sz[v];

         son[u] = max(son[u],sz[v]);

     }

     son[u] = max(son[u],all - son[u]);

     if(son[u] < son[root]) root = u;

 }

 bitset<maxm>bit[maxn],ans;

 void calc(int u,int fa) {

     sz[u] = , bit[u] <<= a[u];

     for(int i = ; i < vec[u].size(); i++) {

         int v = vec[u][i];

         if(used[v] || v == fa) continue;

         bit[v] = bit[u];

         calc(v,u);

         sz[u] += sz[v];

         bit[u] |= bit[v];

     }

 }

 void solve(int u) {

     used[u] = true;

     bit[u].reset(), bit[u].set();

     calc(u,);

     ans |= bit[u];

     for(int i = ; i < vec[u].size(); i++) {

         int v = vec[u][i];

         if(used[v]) continue;

         root = ;

         all = sz[v];

         getroot(v,);

         solve(root);

     }

 }

 int main() {

 #ifdef local

     freopen("data.txt", "r", stdin);

 //    freopen("data.txt", "w", stdout);

 #endif

     int t;

     scanf("%d",&t);

     while(t--) {

         ans.reset();

         scanf("%d%d",&n,&m);

         for(int i = ; i <= n; i++) vec[i].clear(),used[i] = false;

         for(int i = ; i < n; i++) {

             int u,v;

             scanf("%d%d",&u,&v);

             vec[u].push_back(v);

             vec[v].push_back(u);

         }

         for(int i = ; i <= n; i++) scanf("%d",&a[i]);

         root = ;

         son[] = 1e9;

         all = n;

         getroot(,);

         solve(root);

         for(int i = ; i <= m; i++) printf("%d",(int)ans[i]);

         printf("\n");

     }

     return ;

 }