526互联

P4426 [HNOI/AHOI2018] 毒瘤 题解

发布时间 2023-08-05 20:36:55作者: 霜木_Atomic

P4426 [HNOI/AHOI2018] 毒瘤 题解

非常好虚树题目，融合了容斥的内容。

简化题意

给定一张 \(n\) 个点、\(m\) 条边的图，求图的独立集个数。其中 \(n \leq 10^5\)，\(n-1 \leq m \leq n+10\)。
独立集：对于图 \(G(U, E)\) 的一个点集 \(S\)，\(\forall (u, v)\in E\)，不存在 \(u \in S\) 且 \(v \in S\)。换句话讲，就是令图的每一条边的两个端点不会同时被选入一个集合。

思路

首先我们看到了数据范围，发现 \(m\) 和 \(n\) 差的很少，某种意义上，这个图几乎就是一棵树。那么，我们就先从树入手。

如果图是一棵树，那么这个题目就是求树的独立集个数。设 \(f_{u, 1/0}\) 表示选和不选这个点的方案数，转移很明显：

\[ \left\{ \begin{array}{l} f_{u, 0} = \prod_{(u, v) \in E} (f_{v, 0}+f_{v, 1}) \\ f_{u, 1} = \prod_{(u, v) \in E} f_{v, 0} \end{array} \right. \]

然后我们来看看在图上应该怎么做。我们发现，对于所有非树边，不合法的状态只有两个端点全部被选择。这让我们想到容斥。具体的讲，我们算出至少一定数量的边不合法的方案，进行容斥，最后答案就是没有边不合法的方案。

但是，钦定边要枚举子集，自带一个 \(2^{11}\) 次方复杂度；然后每次还要重新 dp，所以总的复杂度是 \(2^{11}n\) ，不太能过去。现在的问题就是如何降低 \(n\) 的复杂度。

我们再来考虑 dp 的过程，发现，每次重新 dp，会有很多信息被重复计算，那就是那些非关键点。这是因为只有关键点会被钦定状态。而关键点非常少，那我们可以考虑建虚树。

我们来考虑虚树上相邻两个点（注意，是虚树上的”点”，而并不一定是关键点），会发现，相邻的两个点的转移总能写成这样的形式：

\[ \left\{ \begin{array}{l} f_{u, 0} = \prod_{(u, v) \in E} (a_vf_{v, 0}+b_vf_{v, 1}) \\ f_{u, 1} = \prod_{(u, v) \in E} (c_vf_{v, 0}+d_vf_{v, 1}) \end{array} \right. \]

这里的系数 \(a, b, c, d\) 是可以通过两次 dp 预处理的。具体来讲，第一次令 \(f_{v, 1}\) 为 \(0\)，第二次令 \(f_{v, 0}\) 为 \(0\)，转移的结果就是系数。

然后……就做完了。
代码：

```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 100500, M = 25;
const int mod = 998244353;

inline int read(){
	int x = 0; char ch = getchar();
	while(ch<'0' || ch>'9') ch = getchar();
	while(ch>='0'&&ch<='9') x = x*10+ch-48, ch = getchar();
	return x;
}
struct node{
	int nxt, to;
};
struct Graph{
	int head[N], tot;
	node edge[N<<1];
	Graph(){
		tot = 0;
		memset(head, 0, sizeof(head));
	}
	void add(int u, int v){
		edge[++tot].nxt = head[u];
		edge[tot].to = v;
		head[u] = tot;
	}
}G1, G2;
int dfn[N];
struct HPD{
private:
	int fa[N], son[N], siz[N], top[N], dep[N], idx;
public: 
	void dfs1(int u, int fath){
		fa[u] = fath;
		dep[u] = dep[fath]+1;
		siz[u] = 1;
		for(int i = G1.head[u]; i; i = G1.edge[i].nxt){
			int v = G1.edge[i].to;
			if(v == fath) continue;
			dfs1(v, u);
			siz[u]+=siz[v];
			if(siz[son[u]] < siz[v]) son[u] = v;
		}
	}
	void dfs2(int u, int Top){
		top[u] = Top;
		dfn[u] = ++idx;
		if(!son[u]) return;
		dfs2(son[u], Top);
		for(int i = G1.head[u]; i; i = G1.edge[i].nxt){
			int v = G1.edge[i].to;
			if(!dfn[v]) dfs2(v, v);
		}
	}
	
	inline int LCA(int x, int y){
		while(top[x] != top[y]){
			if(dep[top[x]] < dep[top[y]]) swap(x, y);
			x = fa[top[x]];
		}
		if(dep[x] > dep[y]) swap(x, y);
		return x;
	}
}th;

int n, m;
struct DSU{
private:
	int fa[N];
public:
	void init(){
		for(int i = 1; i<=n; ++i){
			fa[i] = i;
		} 
	}
	inline int find(int x){
		if(x != fa[x]) fa[x] = find(fa[x]);
		return fa[x];
	}
	bool merge(int x, int y){
		x = find(x), y = find(y);
		if(x == y) return 1;
		fa[x] = y;
		return 0;
	}
}dsu;
int stk[N], p[N], top;
bool is_tar[N];//标记虚树上的点（不一定为关键点） 
int totp;
bool cmp(int x, int y){
	return dfn[x] < dfn[y];
}
void build(){
	sort(p+1, p+totp+1, cmp);
	top = 0;
	stk[++top] = 1, G2.head[1] = 0;
	is_tar[1] = 1; 
	for(int i = 1, lca; i<=totp; ++i){
		if(p[i] == 1) continue;
		lca = th.LCA(stk[top], p[i]);
		if(lca != stk[top]){
			while(dfn[lca] < dfn[stk[top-1]]){
				G2.add(stk[top-1], stk[top]);
				--top; 
			}
			if(dfn[lca] > dfn[stk[top-1]]){
				G2.head[lca] = 0;
				G2.add(lca, stk[top]);
				stk[top] = lca;
				is_tar[lca] = 1; 
			} else{
				G2.add(lca, stk[top]);
				--top;
			}
		}
		G2.head[p[i]] = 0;
		stk[++top] = p[i];
		is_tar[p[i]] = 1;
	}
	for(int i = 1; i<top; ++i){
		G2.add(stk[i], stk[i+1]);
	}
} 
struct Edge{
	int u, v;
}e[M];
int tote;
struct XI{
	int a, b, c, d;
}xi[N];
int f[N][2];
int x_time_y(ll x, ll y){
	return x*y%mod;
}
void x_plus_y(ll &x, ll y){
	x = (x+y)%mod;
	x = (x+mod)%mod;
}
int predfs1(int u, int fath){
	if(is_tar[u]){
		f[u][0] = 1;
		f[u][1] = 0;
		int tmp;
		for(int i = G1.head[u]; i; i = G1.edge[i].nxt){
			int v = G1.edge[i].to;
			if(v == fath) continue;
			tmp = predfs1(v, u);
			if(tmp){
				xi[tmp].a = f[v][0]+f[v][1];
				xi[tmp].c = f[v][0];
			} else{
				f[u][1] = x_time_y(f[u][1], f[v][0]);
				f[u][0] = x_time_y(f[u][0], (1ll*f[v][0]+1ll*f[v][1])%mod);
			}
		}	
		return u;
	} else{
		int tmp = 0, tp = 0;
		f[u][0] = f[u][1] = 1;
		for(int i = G1.head[u]; i; i = G1.edge[i].nxt){
			int v = G1.edge[i].to;
			if(v == fath) continue;
			tmp = predfs1(v, u);
			if(tmp) tp = tmp;
			f[u][1] = x_time_y(f[u][1], f[v][0]);
			f[u][0] = x_time_y(f[u][0], (1ll*f[v][0]+1ll*f[v][1])%mod);
		}
		return tp;
	}
	
}
int predfs2(int u, int fath){
	if(is_tar[u]){
		f[u][0] = 0;
		f[u][1] = 1;
		int tmp;
		for(int i = G1.head[u]; i; i = G1.edge[i].nxt){
			int v = G1.edge[i].to;
			if(v == fath) continue;
			tmp = predfs2(v, u);
			if(tmp){
				xi[tmp].b = f[v][0]+f[v][1];
				xi[tmp].d = f[v][0];
			} else{
				f[u][1] = x_time_y(f[u][1], f[v][0]);
				f[u][0] = x_time_y(f[u][0], (1ll*f[v][0]+1ll*f[v][1])%mod);
			}
		}	
		return u;
	} else{
		int tmp = 0, tp = 0;
		f[u][0] = f[u][1] = 1;
		for(int i = G1.head[u]; i; i = G1.edge[i].nxt){
			int v = G1.edge[i].to;
			if(v == fath) continue;
			tmp = predfs2(v, u);
			if(tmp) tp = tmp;
			f[u][1] = x_time_y(f[u][1], f[v][0]);
			f[u][0] = x_time_y(f[u][0], (1ll*f[v][0]+1ll*f[v][1])%mod);
		}
		return tp;
	}
	
}

bool chs[N];//标记哪些点被强制全选。
void dfs_ans(int u, int fath){
	f[u][1] = f[u][0] = 1;
	if(chs[u]) f[u][0] = 0; 
	for(int i = G2.head[u]; i; i = G2.edge[i].nxt){
		int v = G2.edge[i].to;
		if(v == fath) continue;
		dfs_ans(v, u);
		if(chs[u]){
			f[u][1] = x_time_y(f[u][1], (1ll*xi[v].c*f[v][0]%mod+1ll*xi[v].d*f[v][1]%mod)%mod);
		} else{
			f[u][0] = x_time_y(f[u][0], (1ll*xi[v].a*f[v][0]%mod+1ll*xi[v].b*f[v][1]%mod)%mod);
			f[u][1] = x_time_y(f[u][1], (1ll*xi[v].c*f[v][0]%mod+1ll*xi[v].d*f[v][1]%mod)%mod);		
		}
	}
}
int num[4096]; 
void solve1(){
	th.dfs1(1, 0);
	th.dfs2(1, 1);
	sort(p+1, p+1+totp);
	totp = unique(p+1, p+totp+1)-p-1;
	build();
	predfs1(1, 0);
	xi[1].a = f[1][0]+f[1][1];
	xi[1].c = f[1][0];
	predfs2(1, 0);
	xi[1].b = f[1][0]+f[1][1];
	xi[1].d = f[1][0];
	int S = (1<<tote)-1;
	for(int i = 1; i<=S; ++i){
		num[i] = num[i>>1]+(i&1);
	}
	ll ans = 0;
	for(int s = 0; s<=S; ++s){
		int fu = (num[s] & 1)?-1:1;
		for(int i = 1; i<=tote; ++i){
			if((s>>(i-1)) & 1){
				chs[e[i].u] = 1;
				chs[e[i].v] = 1;
			}
		}
		dfs_ans(1, 0);
//		int tmp = 1ll*fu*(1ll*xi[1].a*f[1][0]%mod+1ll*xi[1].b*f[1][1]%mod)%mod;
//		cout << tmp << endl;
		x_plus_y(ans, 1ll*fu*(1ll*xi[1].a*f[1][0]%mod+1ll*xi[1].b*f[1][1]%mod)%mod);
		for(int i = 1; i<=tote; ++i){
			if((s>>(i-1)) & 1){
				chs[e[i].u] = 0;
				chs[e[i].v] = 0;
			}
		}
	}
	ans = (1ll*ans+mod)%mod;
	printf("%d\n", ans);
}
void dfs(int u, int fath){
	f[u][0] = f[u][1] = 1;
	for(int i = G1.head[u]; i;i = G1.edge[i].nxt){
		int v = G1.edge[i].to;
		if(v == fath) continue;
		dfs(v, u);
		f[u][0] = x_time_y(f[u][0], (1ll*f[v][0]+1ll*f[v][1])%mod);
		f[u][1] = x_time_y(f[u][1], f[v][0]);
	} 
}
void solve2(){
	dfs(1, 0);
	printf("%d\n", (1ll*f[1][0]+1ll*f[1][1])%mod);
} 
void printa(){
	puts("");
	for(int u = 1; u<=n; ++u){
		for(int i = G1.head[u]; i; i = G1.edge[i].nxt){
			printf("%d %d\n", u, G1.edge[i].to);
		}
	}
	puts("");
}

void printb(){
	puts("");
	for(int u = 1; u<=n; ++u){
		if(is_tar[u]){
			for(int i = G2.head[u]; i; i = G2.edge[i].nxt){
				printf("%d %d\n", u, G2.edge[i].to);
			}
		}
	}
	puts("");
}
int main(){
	n = read(), m = read();
	dsu.init();
	for(int i = 1; i<=m; ++i){
		int u = read(), v = read();
		if(dsu.merge(u, v)){
			e[++tote] = {u, v};
			p[++totp] = u;
			p[++totp] = v;
//			is_tar[u] = 1;
//			is_tar[v] = 1;
		} else {
			G1.add(u, v);
			G1.add(v, u);
		}
	}
	if(tote){
		solve1();
	} else{
		solve2();
	}
//	printa();
//	printb();
	return 0;
}