【点分治 DP】2017 CCPC Hangzhou E. Master of Subgraph
2021-10-25 20:00:00 # ACM

题链

题目解析

给定一颗树，求是否存在某一连通子图的点权和等于 i；

点分治，求包含重心的连通子图的所有权值和；

此时转化为树形DP问题，将重心作为根，因为是连通子图，所以若某一点被选择，那么它的父亲都要被选择；

设 bitset<m> dp[i] 表示选择 i 号节点能得到得所有权值；

转移公式： dp[u] = (dp[v1] | dp[v2] | … | dp[vk]) << w[u]， v 是 u 的孩子节点；
注意 dfs 到当前 u 节点时，需要将根节点到 u 节点的路径和计算上；

需要的信息就是 dp[root] 的信息，将 ans |= dp[root]；

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
	#define gg(x) cout << #x << ": " << x << "\n";
	#define LL long long
	#define ULL unsigned long long
	#define Pair pair<int ,int >
	#define ls rt<<1
	#define rs rt<<1|1
	#define PI acos(-1.0)
	#define eps 1e-8
	#define fi first
	#define se second
	#define ll long long

const int mod = 998244353;
const int MAXN = 2e9;
const int MS = 3009;

int n,m,k;
vector<int > vc[MS];
int val[MS];
int w[MS], sz[MS], tr_size, rt;
int vis[MS];
bitset<100009> dp[MS], ans;

void get_root(int u, int f){
	sz[u] = 1;
	w[u] = 0;
	for(auto v:vc[u]){
		if(v != f && !vis[v]){
			get_root(v,u);
			sz[u] += sz[v];
			w[u] = max(w[u], sz[v]);
		}
	}
	w[u] = max(w[u], tr_size-sz[u]);
	if(w[u] < w[rt]) rt = u;
}

void dfs(int u, int f){
	dp[u] <<= val[u];
	for(auto v:vc[u]){
		if(v != f && !vis[v]){
			dp[v] = dp[u];
			dfs(v, u);
			dp[u] |= dp[v];
		}
	}
}

void divide(int u, int f){
	vis[u] = 1;
	dp[u].reset(); dp[u][0] = 1;
	dfs(u, 0);
	ans |= dp[u];
	for(auto v:vc[u]){
		if(v != f && !vis[v]){
			w[rt = 0] = tr_size = sz[v];
			get_root(v, 0);
			get_root(rt, 0);
			divide(rt, 0);
		}
	}
}

void clear(){
	ans.reset();
	memset(vis, 0, sizeof vis);
	for(int i=1;i<=n;i++){
		vc[i].clear();
	}
}

void solve(){
	cin >> n >> m;
	for(int i=2;i<=n;i++){
		int u,v; cin >> u >> v;
		vc[u].push_back(v);
		vc[v].push_back(u);
	}
	for(int i=1;i<=n;i++) cin >> val[i];
	w[rt = 0] = tr_size = n;
	get_root(1, 0);
	get_root(rt, 0);
	divide(rt, 0);
	for(int i=1;i<=m;i++){
		cout << ans[i];
	}
	cout << "\n";
	clear();
}

int main() {
	ios::sync_with_stdio(false);
	int ce = 1;
	cin >> ce;
	while(ce--) solve();

	return 0;
}
Prev
2021-10-25 20:00:00 # ACM
Next