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;
}