前置知识点：虚树，dp。
题意
给定一个 \(n\) 个点 \(m\) 条边的无向简单联通图，满足 \(n - 1 \le m \le n + 10\)。求图的独立集个数，对 \(998244353\) 取模。
题解
首先，注意到 \(m \le n + 10\)，也就是说非树边只有最多 \(11\) 条。将这些非树边连接的 \(s=22\) 个点（下面称为关键点）找出来，接着 \(2^s\) 枚举每个关键点的状态，最后对整棵树树形 dp 就可以在 \(\mathcal{O}(n2^s)\) 复杂度下解决这个问题，可以得到 70+pts 的好成绩。
于是沿着这一条思路，可以想办法优化。我们先将朴素树形 dp 给推出，设 \(f_{x, 0 / 1}\) 表示 \(x\) 为根的子树中 \(x\) 选或不选的方案数。那么有：
\[\begin{cases} f_{x, 0} = \prod\limits_{v \in x.\text{son}} (f_{v, 0} + f_{v, 1})\\ f_{x, 1} = \prod\limits_{v \in x.\text{son}} f_{v, 0} \end{cases} \]接着我们建出关键点的虚树，对于虚树上的一条边 \((x, v)\)，我们发现 \(f_{v, 0 / 1}\) 对 \(x\) 的贡献竟然可以这么表示 \(f_{x, 0 / 1} *= (k_0 \cdot f_{v, 0} + k_1 \cdot f_{v, 1})\)。并且由于在枚举关键点状态时，虚树的状态不会改变，所以 \(k_0, k_1\) 是个定值！
这样我们就可以在 \(\mathcal{O}(2^s)\) 枚举前，预处理出来系数，接着在虚树上 \(\mathcal{O}(s)\) dp 就行了。总复杂度 \(\mathcal{O}(s2^s)\)。
下面详细讲一下系数是怎么推出来的。对于虚树上的一条边 \((x, y)\)，在原树上从 \(y\) 一步一步跳到 \(x\)，这样复杂度显然是 \(\mathcal{O}(n)\)。记 \(p_i\) 表示 \(v\) 的 \(i\) 级祖先。\(k\) 表示系数，有：
\[\begin{cases} f_{p_i, 0} = f_{p_i, 0}' \times (k_{p_i, 0, 0} \times f_{v, 0} + k_{p_i, 0, 1} \times f_{v, 1}) \\ f_{p_i, 1} = f_{p_i, 1}' \times (k_{p_i, 1, 0} \times f_{v, 0} + k_{p_i, 1, 1} \times f_{v, 1}) \end{cases} \]所以 \(k_{p_i, 0/1, 0/1}\) 和 \(k_{p_{i + 1}, 0/1, 0/1}\) 的关系式只需暴力展开得到：
\[\begin{cases} \begin{aligned} f_{p_{i + 1}, 0} &= f_{p_{i + 1}, 0}' \times (f_{p_i, 0} + f_{p_i, 1})\\ &=f_{p_{i + 1}, 0}' \times \left[f_{p_i, 0}' \times (k_{p_i, 0, 0} \times f_{v, 0} + k_{p_i, 0, 1} \times f_{v, 1}) + f_{p_i, 1}' \times (k_{p_i, 1, 0} \times f_{v, 0} + k_{p_i, 1, 1} \times f_{v, 1})\right]\\ &=f_{p_{i + 1}, 0}'\times\left[(f_{p_i, 0}' \times k_{p_i, 0, 0} + f_{p_i, 1}' \times k_{p_i, 1, 0})\times f_{v, 0} + (f_{p_i, 0}' \times k_{p_i, 0, 1} + f_{p_i, 1}' \times k_{p_i, 1, 1}) \times f_{v, 1}\right] \\ &\Rightarrow \begin{cases} k_{p_{i + 1}, 0, 0} = f_{p_i, 0}' \times k_{p_i, 0, 0} + f_{p_i, 1}' \times k_{p_i, 1, 0} \\ k_{p_{i + 1}, 0, 1} = f_{p_i, 0}' \times k_{p_i, 0, 1} + f_{p_i, 1}' \times k_{p_i, 1, 1} \end{cases} \end{aligned} \\ \begin{aligned} f_{p_{i + 1}, 1} &= f_{p_{i + 1}, 1}' \times f_{p_i, 0} \\ &= f_{p_{i + 1}, 1}' \times \left[ f_{p_i, 0}' \times (k_{p_i, 0, 0} \times f_{v, 0} + k_{p_i, 0, 1} \times f_{v, 1}) \right] \\ &= f_{p_{i + 1}, 1}' \times \left[(f_{p_i, 0}' \times k_{p_i, 0, 0}) \times f_{v, 0} + (f_{p_i, 0}' \times k_{p_i, 0, 1}) \times f_{v, 1}\right]\\ &\Rightarrow \begin{cases} k_{p_{i + 1}, 1, 0} = f_{p_i, 0}' \times k_{p_i, 0, 0} \\ k_{p_{i + 1}, 1, 1} = f_{p_i, 0}' \times k_{p_i, 0, 1} \end{cases} \end{aligned} \end{cases} \]整理得：
\[\begin{cases} k_{p_{i + 1}, 0, 0} = f_{p_i, 0}' \times k_{p_i, 0, 0} + f_{p_i, 1}' \times k_{p_i, 1, 0} \\ k_{p_{i + 1}, 0, 1} = f_{p_i, 0}' \times k_{p_i, 0, 1} + f_{p_i, 1}' \times k_{p_i, 1, 1} \\ k_{p_{i + 1}, 1, 0} = f_{p_i, 0}' \times k_{p_i, 0, 0} \\ k_{p_{i + 1}, 1, 1} = f_{p_i, 0}' \times k_{p_i, 0, 1} \end{cases} \] 标签：begin,end,笔记,times,毒瘤,mathcal,cases,P4426,dp From： https://www.cnblogs.com/CTHOOH/p/17999977