HDU 6268 Master of Subgraph （2017 CCPC 杭州 E题，树分治 + 树上背包）

题目链接  2017 CCPC Hangzhou  Problem E

题意  给定一棵树，每个点有一个权值，现在我们可以选一些连通的点，并且把这点选出来的点的权值相加，得到一个和。

求$[1, m]$里面哪些值可以被表示成选出来的点的权值和。用$01$序列的方式输出。

重现赛赛场上的我英勇无畏，大胆做$3000$次FFT合并两个bitset表示的答案。

然后TLE到结束（活该）

其实这个题确实要用bitset，关键是能不能把合并两个bitset转化成合并一个数和一个bitset。

考虑点分治。我们先选出树的重心，然后考虑一定要选这个点的答案。

然后这道题的关键来了。

假设我选择了某个点，那么我必须选择这个点的父亲。

现在开始递归这棵树。每次递归到一个点，这个点的bitset初值化为父亲结点表示的bitset右移$w[x]$位。

他的意义是，当前这个点如果选了，那么他的父亲必选，那也就是求他父亲当前求得的答案集合结合这个点的权值的答案。

然后回溯的时候，父亲表示的bitset要或上儿子表示的bitset。

这是因为在后面这个父亲的其他儿子求解的之后，要用到这个父亲已经求得的信息，并结合起来，

通过这个父亲起到连接的效果。

最后以当前这个分治中心为根的树的答案就是分治中心表示的bitset。

那么接下来继续往下递归求解就可以了。

时间复杂度$O(nlogn \cdot \frac{m}{w})$

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b)	for (int i(a); i <= (b); ++i)

#define dec(i, a, b)	for (int i(a); i >= (b); --i)

const int N = 3e3 + 10;

const int M = 1e5 + 10;

int T;

int n, m;

int et;

int f[N], w[N], sz[N], vis[N];

int root, sum;

int cnt;

vector <int> v[N];

bitset <M> b[N], ans;

void getroot(int x, int fa){

	sz[x] = 1;

	f[x]  = 0;

	for (auto u : v[x]){

		if (u == fa || vis[u]) continue;

		getroot(u, x);

		sz[x] += sz[u];

		f[x] = max(f[x], sz[u]);

	}

	f[x] = max(f[x], sum - sz[x]);

	if (f[x] < f[root]) root = x;

}

void calc(int x, int fa, int now){

	cnt ^= 1;

	b[cnt] = b[cnt ^ 1];

	b[cnt] |= (b[cnt ^ 1] << now);

	for (auto u : v[x]){

		if (vis[u] || u == fa) continue;

		calc(u, x, w[u]);

	}

}	

void dp(int x, int fa){

	b[x] = b[fa] << w[x];

	for (auto u : v[x]){

		if (vis[u] || u == fa) continue;

		dp(u, x);

		b[x] |= b[u];

	}

}

void calcsize(int x, int fa){

	sz[x] = 1;

	b[x].reset();

	for (auto u : v[x]){

		if (vis[u] || u == fa) continue;

		calcsize(u, x);

		sz[x] += sz[u];

	}

}

void solve(int x){

	++et;

	vis[x] = 1;

	b[0].reset();

	b[0].set(0);

	calcsize(x, 0);

	dp(x, 0);

	ans |= b[x];

	for (auto u : v[x]){

		if (vis[u]) continue;

		sum = sz[u];

		f[0] = n + 1;

		getroot(u, root = 0);

		solve(root);

	}

}		

int main(){

	scanf("%d", &T);

	while (T--){

		ans.reset();

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

		rep(i, 0, n + 1) v[i].clear();

		et = 0;

		rep(i, 2, n){

			int x, y;

			scanf("%d%d", &x, &y);

			v[x].push_back(y);

			v[y].push_back(x);

		}

		rep(i, 1, n) scanf("%d", w + i);

		memset(vis, 0, sizeof vis);

		f[0] = n + 1;

		sum = n;

		getroot(1, root = 0);

		solve(root);

		rep(i, 1, m) if (ans[i]) putchar(49);

		else putchar(48);

		putchar(10);

	}

	return 0;

}

HDU 6268 Master of Subgraph （2017 CCPC 杭州 E题，树分治 + 树上背包）的相关教程结束。