題面

方法一

首先預處理每個子集是否成團，然后枚舉子集即可 \(O(3^n+n2^n)\)。

方法二

考慮 meet in the middle，左側處理處每個子集是否成團，右側處理每個子集是否成團，然后枚舉其子集成團數量，最后在枚舉左側合法子集，貢獻是這個子集關于右側集合的合法集合的子集成團數量，你可以左側開大一點，右側開小一點 \(O(x2^x+3^{n-x}+(n-x)2^{n-x})\)，其中 \(x\) 自選。

方法三

考慮優化右側枚舉子集。如果設計 \(f_i\) 表示集合 \(i\) 的合法子集數量, \(to_i\) 表示 \(i\) 的連通集，那么我們發現如下方程：

所以就可以 \(O(\frac{n}{2}2^{\frac{n}{2}})\) 做了。