[HDU6268]Master of Subgraph

[HDU6268]Master of Subgraph

题目大意：

一棵\(n(n\le3000)\)个结点的树，每个结点的权值为\(w_i\)。给定\(m(m\le10^5)\)，对于任意\(i\in[1,m]\)，问书中是否有一个连通子图的权值和等于\(i\)。

思路：

重心剖分。考虑处理当前处理出的以重心\(x\)为根的子树。首先求出当前子树的DFS序，设用\(node[i]\)表示DFS序为\(i\)的结点编号。考虑动态规划，用\(f[i][j]\)（std::bitset<M> f[N]）表示包含DFS序为\(i\)的结点，是否有权值和为\(j\)的连通子图。设当前结点为\(x\)，枚举子结点\(y_{1\sim k}\)，则转移方程为\(f[x]=(f[y_1]\vee f[y_2]\vee\ldots\vee f[y_k])<<w[x]\)。

由于事实上对于每一个\(x\)，我们并不需要知道\(f[x]\)，而只需要利用它们求出\(f[root]\)的值，因此我们对于每一个\(x\)可以和上一个计算过的同级兄弟结点\(node[dfn[x]+sz[x]]\)合并。按DFS倒序枚举每一个结点\(x\)，其DFS序为\(i\)。此时的状态转移方程为\(f[i]=(f[i+1]<<w[x])|f[i+sz[x]]\)。时间复杂度\(\mathcal O(\frac{nm\log n}\omega)\)。

源代码：

#include<cstdio>
#include<cctype>
#include<bitset>
#include<forward_list>
inline int getint() {register char ch;while(!isdigit(ch=getchar()));register int x=ch^'0';while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');return x;
}
constexpr int N=3001,M=1e5+1;
bool vis[N];
std::forward_list<int> e[N];
std::bitset<M> ans,f[N];
int n,m,w[N],size[N],sz[N],node[N],dfn[N],root,whole,min;
inline void add_edge(const int &u,const int &v) {e[u].emplace_front(v);e[v].emplace_front(u);
}
inline void clear() {ans.reset();for(register int i=1;i<=n;i++) {vis[i]=false;e[i].clear();}
}
void dfs_root(const int &x,const int &par) {size[x]=1;int max=0;for(auto &y:e[x]) {if(y==par||vis[y]) continue;dfs_root(y,x);size[x]+=size[y];max=std::max(max,size[y]);}max=std::max(max,whole-size[x]);if(max<min) {min=max;root=x;}
}
inline void get_root(const int &x,const int &sum) {root=0;min=n+1;whole=sum;dfs_root(x,0);vis[root]=true;
}
void dfs(const int &x,const int &par) {sz[x]=1;dfn[x]=dfn[0]++;node[dfn[x]]=x;for(auto &y:e[x]) {if(y==par||vis[y]) continue;dfs(y,x);sz[x]+=sz[y];}
}
void solve(const int &x) {dfn[0]=0;dfs(x,0);f[dfn[0]]=1;for(register int i=dfn[0]-1;~i;i--) {const int &y=node[i];f[i]=(f[i+1]<<w[y])|f[i+sz[y]];}ans|=f[0];for(auto &y:e[x]) {if(vis[y]) continue;get_root(y,size[y]);solve(root);}
}
int main() {for(register int T=getint();T;T--) {n=getint(),m=getint();for(register int i=1;i<n;i++) {add_edge(getint(),getint());}for(register int i=1;i<=n;i++) {w[i]=getint();}get_root(1,n);solve(root);for(register int i=1;i<=m;i++) {printf("%d",(int)ans[i]);}putchar('\n');clear();}return 0;
}