Description：

给一棵树和不超过 $11$ 条非树边，求最大独立集。

$1\leqslant n\leqslant 10^5$

Solution：

我们首先考虑一个暴力，对于一条非树边，他两端的点有 $3$ 种选法： $(0,1),(1,0),(0,0)$ ，那么我们可以 $3^{11}$ 枚举这些点的选择情况，然后每次树形 $DP$ ，特殊转移一下这些点就行了，这样的复杂度是 $O(3^{11}n)$ 。

我们考虑优化这个过程，会发现转移方程一定可以写成： $$ f[i][0/1]=\prod_{v\in son[i]}(k[v][0/1][0]f[v][0]+k[v][0/1][1]f[v][1])\times val[i][0/1] $$ 那么我们可以建出这 $22$ 个点的虚树，然后对于每条虚树上的边预处理 $k[v][0/1][0/1]$ ，然后还是 $3^{11}$ 枚举特殊点的选择，然后在虚树上按 $k$ 树形 $DP$ 就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

int n,m;

#define MAXN 100100

#define MOD 998244353

struct edge

{

	int to,nxt;

}ge[MAXN << 1];

int gedgenum = 0;

int glin[MAXN] = {0};

void gadd(int a,int b)

{

	ge[++gedgenum] = (edge){b,glin[a]};glin[a] = gedgenum;

	ge[++gedgenum] = (edge){a,glin[b]};glin[b] = gedgenum;

	return;

}

edge e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

	return;

}

struct edges

{

	int u,v;

}es[20];

int ecnt = 0;

bool vis[MAXN];

bool tag[MAXN];

int p[MAXN],id[MAXN];

void prework(int k,int fa)

{

	vis[k] = true;

	for(int i = glin[k];i != 0;i = ge[i].nxt)

	{

		if(ge[i].to == fa)continue;

		if(vis[ge[i].to])

		{

			if(!tag[((i - 1) ^ 1) + 1])

			{

				es[++ecnt] = (edges){k,ge[i].to};

				p[++p[0]] = k;p[++p[0]] = ge[i].to;

				tag[i] = true;

			}

		}

		else

		{

			add(k,ge[i].to);

			prework(ge[i].to,k);

		}

	}

	return;

}

int top[MAXN],dep[MAXN],siz[MAXN],son[MAXN],fa[MAXN];

int dfn[MAXN],tot = 0;

void dfs1(int k,int depth)

{

	dep[k] = depth;

	siz[k] = 1;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fa[k])

		{

			fa[e[i].to] = k;

			dfs1(e[i].to,depth + 1);

			siz[k] += siz[e[i].to];

			if(son[k] == 0 || siz[e[i].to] > siz[son[k]])son[k] = e[i].to;

		}

	}

	return;

}

void dfs2(int k,int tp)

{

	dfn[k] = ++tot;

	top[k] = tp;

	if(son[k] == 0)return;

	dfs2(son[k],tp);

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fa[k] && e[i].to != son[k])

		{

			dfs2(e[i].to,e[i].to);

		}

	}

	return;

}

int LCA(int a,int b)

{

	while(top[a] != top[b])

	{

		if(dep[top[a]] < dep[top[b]])swap(a,b);

		a = fa[top[a]];

	}

	return (dep[a] < dep[b] ? a : b);

}

bool cmp_dfn(int a,int b){return dfn[a] < dfn[b];}

int stack[MAXN],tp = 0;

edge te[MAXN];

int tedgenum = 0;

int tlin[MAXN] = {0};

bool mark[MAXN];

void tadd(int a,int b)

{

	mark[a] = mark[b] = true;

	te[++tedgenum] = (edge){b,tlin[a]};tlin[a] = tedgenum;

	return;

}

int rt;

int val[MAXN][2];

int v[MAXN][2][2];

int calc(int k,int fa)

{

	val[k][0] = val[k][1] = 1;

	if(mark[k])

	{

		v[k][0][0] = v[k][1][0] = v[k][0][1] = 1;

		v[k][1][1] = 0;

	}

	int sch = 0;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to == fa)continue;

		int ch = calc(e[i].to,k);

		if(ch == 0)

		{

			val[k][0] = 1ll * val[k][0] * (val[e[i].to][0] + val[e[i].to][1]) % MOD;

			val[k][1] = 1ll * val[k][1] * val[e[i].to][0] % MOD;

		}

		else

		{

			sch = ch;

			if(!mark[e[i].to])

			{

				int v00 = v[ch][0][0],v01 = v[ch][0][1],v10 = v[ch][1][0],v11 = v[ch][1][1];

				v[ch][0][0] = (1ll * v00 * val[e[i].to][0] + 1ll * v10 * val[e[i].to][1]) % MOD;

				v[ch][0][1] = (1ll * v01 * val[e[i].to][0] + 1ll * v11 * val[e[i].to][1]) % MOD;

				v[ch][1][0] = 1ll * v00 * val[e[i].to][0] % MOD;

				v[ch][1][1] = 1ll * v01 * val[e[i].to][0] % MOD;

			}

		}

	}

	return (mark[k] ? k : sch);

}

int bit(int s,int k){return ((s >> (k - 1)) & 1);}

int state;

int f[MAXN][2];

bool spe[MAXN];

void dp(int k)

{

	f[k][0] = val[k][0];f[k][1] = val[k][1];

	for(int i = tlin[k];i != 0;i = te[i].nxt)

	{

		dp(te[i].to);

		f[k][0] = 1ll * f[k][0] * (1ll * v[te[i].to][0][0] * f[te[i].to][0] % MOD + 1ll * v[te[i].to][0][1] * f[te[i].to][1] % MOD) % MOD;

		f[k][1] = 1ll * f[k][1] * (1ll * v[te[i].to][1][0] * f[te[i].to][0] % MOD + 1ll * v[te[i].to][1][1] * f[te[i].to][1] % MOD) % MOD;

	}

	if(spe[k])

	{

		if(bit(state,id[k]) == 0)f[k][1] = 0;

		if(bit(state,id[k]) == 1)f[k][0] = 0;

	}

	return;

}

void dp(int k,int fa)

{

	f[k][0] = f[k][1] = 1;

	for(int i = glin[k];i != 0;i = ge[i].nxt)

	{

		if(ge[i].to == fa)continue;

		dp(ge[i].to,k);

		f[k][0] = 1ll * f[k][0] * (f[ge[i].to][0] + f[ge[i].to][1]) % MOD;

		f[k][1] = 1ll * f[k][1] * f[ge[i].to][0] % MOD;

	}

	return;

}

int main()

{

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

	for(int i = 1;i <= m;++i)gadd(rd(),rd());

	if(m == n - 1)

	{

		dp(1,0);

		cout << (f[1][0] + f[1][1]) % MOD << endl;

		return 0;

	}

	prework(1,0);

	sort(p + 1,p + 1 + p[0]);

	p[0] = unique(p + 1,p + 1 + p[0]) - p - 1;

	int tot = (1 << p[0]) - 1;

	dfs1(1,1);dfs2(1,1);

	sort(p + 1,p + 1 + p[0],cmp_dfn);

	for(int i = 1;i <= p[0];++i)spe[p[i]] = true;

	stack[++tp] = p[1];

	for(int i = 2;i <= p[0];++i)

	{

		int lca = LCA(stack[tp],p[i]);

		if(lca == stack[tp])

		{

			stack[++tp] = p[i];

			continue;

		}

		while(tp >= 2)

		{

			if(dfn[lca] < dfn[stack[tp - 1]])

			{

				tadd(stack[tp - 1],stack[tp]);

				--tp;

			}

			else

			{

				tadd(lca,stack[tp]);

				--tp;

				break;

			}

		}

		if(tp == 1 && dfn[lca] < dfn[stack[tp]])

		{

			tadd(lca,stack[tp]);

			stack[tp] = lca;

		}

		if(lca != stack[tp])stack[++tp] = lca;

		stack[++tp] = p[i];

	}

	while(tp >= 2)

	{

		tadd(stack[tp - 1],stack[tp]);

		--tp;

	}

	rt = stack[1];

	calc(rt,0);

	int ans = 0;

	for(int i = 1;i <= p[0];++i)id[p[i]] = i;

	for(int i = 0;i <= tot;++i)

	{

		bool tag = true;

		for(int x = 1;x <= ecnt;++x)

		{

			if(bit(i,id[es[x].u]) && bit(i,id[es[x].v]))

			{

				tag = false;

				break;

			}

		}

		if(!tag)continue;

		state = i;

		dp(rt);

		ans = (ans + (f[rt][0] + f[rt][1]) % MOD) % MOD;

	}

	cout << ans << endl;

	return 0;

}