HDUOJ 6268 Master of Subgraph

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

题意：给你一棵树，每个节点有自己的价值 $w_i$ ，给定一个数字 $m$ ，问 $1-m$ 这 $m$ 个数字是否能用一个联通子图的价值和表示出来，能输出 $1$ 否则输出 $0$ 。

思路：先不考虑联通子图这个问题，那么整个问题就是一个裸的树形背包问题，我们把树的 $dfs$ 序建立出来，对于 $dfs$ 序上的每一个点，考虑如果自己选那么自己子树内就可以选，否则只有在这棵子树外面才可以选。设 $dp[i][j]$ 为 $dfs$ 序上 $[i,n]$ 位置对应的节点背包容量为 $j$ 是否能被表示出来，对于位置 $i$ ，如果选我们就从 $dp[i+1]$ 转移过来，不选我们就从 $dp[i+sz[id[i]]]$ 这个位置转移过来， $id[i]$ 表示 $dfs$ 序为 $i$ 的节点编号是什么, $sz[id[i]]$ 表示这个节点的子树大小是多少，从后往前进行 $dp$ ，最终 $dp[1]$ 就是以 $x$ 为根的树形背包的答案。考虑到需要联通子图，不能是一块一块的，我们即用点分治，每次求出包含重心的答案，然后递归下去即可，由于这里的 $m$ 很大，所以 $01$ 背包要用 $bitset$ 优化，时间复杂度 $O(\frac{nmlogn}{64})$ 。

#include <bits/stdc++.h>
#define PB push_back
#define MP make_pair 
using namespace std;
template<typename T>
inline T read(T&x){
	x=0;int f=0;char ch=getchar();
	while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
	while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return x=f?-x:x;
}
const int N=3000+10;
int T,n,m,u,v,i,root,tot,sum,f[N],w[N],sz[N],sz2[N],val[N],id[N];
bool vis[N];
vector<int>G[N];
bitset<100005>g[N],res;
void getroot(int u,int fa){
	sz[u]=1,f[u]=0;
	for (int i=0;i<(int)G[u].size();i++){
		int v=G[u][i];
		if (v==fa || vis[v]) continue;
		getroot(v,u);
		sz[u]+=sz[v];
		f[u]=max(f[u],sz[v]);
	}
	f[u]=max(f[u],sum-sz[u]);
	if (f[u]<f[root]) root=u;
}
void dfs(int u,int fa){
	sz2[u]=1,val[++tot]=u,id[u]=tot;
	for (int i=0;i<(int)G[u].size();i++){
		int v=G[u][i];
		if (v==fa || vis[v]) continue;
		dfs(v,u);
		sz2[u]+=sz2[v];
	}
}
void solve(int u){
	vis[u]=1,tot=0,dfs(u,0);
	int i;
	for (i=1;i<=tot+1;i++) g[i].reset();
	g[tot+1].set(0);
	for (i=tot;i>=1;i--){
		int u=val[i];
		g[i]|=g[i+1]<<w[u];
		g[i]|=g[i+sz2[u]];
	}
	res|=g[1];
	for (i=0;i<(int)G[u].size();i++){
		int v=G[u][i];
		if (vis[v]) continue;
		sum=sz[v],root=0;
		getroot(v,0);
		solve(root);
	}
}
int main(){
	for (read(T);T--;){
		read(n),read(m);
		for (i=1;i<=n;i++) G[i].clear(),vis[i]=0;
		for (i=1;i<n;i++){
			read(u),read(v);
			G[u].PB(v);
			G[v].PB(u);
		}
		for (i=1;i<=n;i++) read(w[i]);
		res.reset(),sum=n,root=0,f[0]=n+1;
		getroot(1,0);
		solve(root);
		for (i=1;i<=m;i++) printf("%d",res[i]?1:0);
		puts(""); 
	}
	return 0;
}

Written by Yiming Pan who lives and works in Hangzhou China. Welcome follow me on Github

Cannot load comments. Please check you network.