考虑通过容斥删边，转换为树的拓扑序。
先考虑怎么计算树的拓扑序，这个方法是将所有儿子指向父亲的边删去，容斥为父亲指向儿子的边。
容易发现只要有删去的边就需要乘上多重集组合数 $\binom{2^{k+1}}{\dots}$，这个东西模 $2$ 是 $0$，因此只有不删边的情况有贡献，又因为 $-1\equiv 1\pmod 2$，因此所有树边方向都是不重要的，我们只关心将树边全部改为父亲指向儿子后，树的拓扑序个数。
也即，我们只关心树的形态。
考虑部分分，讨论每个格子（记为 $\binom{1,2}{3,4}$），不妨设边的方向是 $3\to 1,2\to 4$，容易发现只有三个情况：
- 环，答案为 $0$。
- $1\to 2,3\to 4$，此时拓扑序确定，可以删去 $3\to 4$，对拓扑序没有影响。
- $2\to 1,3\to 4$，容斥，删去 $3\to 4$ 的边，再减去 $4\to 3$ 的情况，$4\to 3$ 的情况和上面情况相同。
因此做容斥 DP，先考虑树的拓扑序怎么计算，直接树上背包，$dp_{u}=\binom{sz_u-1}{\dots}\prod\limits_{v\in \text{son}(u)} dp_{v}$。
在本问题中，每个点只有两个儿子，且因为至少删一个横边，所以至少一个儿子子树大小为 $1$。因此 DP 不用额外记录子树大小，复杂度是 $O(2^{k})$ 的。
考虑有竖向边同向怎么做，将竖边继续容斥，改成【删去】减去【反向】，反向的情况就是竖向边方向不同的情况，然后做法和上面一样。因为这样可能删除竖向边，所以【至少一个儿子子树大小为 $1$】的性质没了。
画图发现，一个点较小的子树大小只和【上一个竖边在哪】和【上一个保留竖边的格子删除了上横边还是下横边】，在 DP 的时候记录，$dp_{i,j,0/1}$ 表示前 $i$ 个竖边，上一个竖边在 $j$，上一个竖边保留处删掉了哪个横边。在保留竖向边处结算贡献（因为删除竖向边的部分每个点只有一个儿子），可以做到 $O(4^k)$。
考虑优化，容易发现对于 $dp_{i,i}\to dp_{i+1,i+1}$ 的转移系数模 $2$ 是 $1$，$dp_{i,j}\to dp_{i+1,j}$ 的系数也是 $1$，$dp_{i,j}\to dp_{i+1,i+1}$ 的转移，系数是组合数 $\binom{2i+1}{\dots}$，根据 Lucas 定理，只需要枚举 $2i+1$ 在二进制下的子集，即可确定系数非 $0$ 的 $j$。
因此滚动数组避免前两个转移，将复杂度优化到 $O(3^k)$。
模 $2$ 意义下，加法相当于异或，乘法相当于按位与，因此可以做到 $O(\frac{3^k}{w})$，总复杂度 $O(\frac{T3^k}{w})$。
滚动数组需要支持快速清空，清空需要打 $tag$，而且可能需要序列并查集等轻量 DS 维护。