【玫瑰】【玫瑰】

WeWantToRun · 2024-08-23 16:09:03 · 题解

感觉非常牛。

手玩一下可以发现，对于一棵树，任意一个包含偶数个点的点集对应唯一一种选边的方式。对于基环树，显然会有两种。容易推出对于 n 个点 m 条边的树，每个点集均有 2^{m-n+1} 种选边方式。

然后对于多个联通块的情况就当一个分组背包计数即可。时间复杂度 O(n^2)。