建造军营

subtask1

\(O(2^{n+m})\) 暴力，可以获得 \(15\) 分。

subtask2

考虑 sub1 中的 check 方式就是考虑两点是否存在两条边不重复路径，这启发我们缩 ecc。

缩掉 ecc 后进行 dp 计数。\(dp_{i,0/1}\) 代表考虑 \(i\) 的子树，\(i\) 选或不选的方案数。注意由于已经缩掉了 ecc，则 \(i\) 选择的方案数有 \(2^{n'_i+m'_i}-2^{m'_i}\)，其中 \(n'_i\) 和 \(m'_i\) 分别为该 ecc 的点数、边数。将该式子记作 \(f_i\)。

首先考虑 \(dp_{i,1}\) 的转移：\(dp_{i,1}=f_i\times\sum\limits_{p\in son,q=son/p}\sum\limits_{j=1}^{|p|}dp_{p_j,1}\times\sum\limits_{j=1}^{|q|}g_{q_j}\)。

其中 \(g_i=dp_{i,0}\times 2\)。

考虑 \(dp_{i,0}\) 的转移：\(dp_{i,0}=\sum\limits_{p\in son}(dp_{p,1}\times 4\times\sum\limits_{q\in son,q\neq p}dp_{q,0})+2^{son}\)。

这可以进行 \(O(\sum\limits_{i}2^{son_i})\) 的 dp，综合上 sub1 可以获得 \(45\) 分，观察到特殊性质A 可以通过。