C - Forest

直接暴力也能做。

首先，最小生成树的算法依赖于先对边权进行一次排序，所以首先对所有边进行一次从小到大的排序，每次通过新加一条边更新维护的信息，此时得到的一定是最小生成树。

直接计算最小生成森林的相关信息比较困难，考虑计算每个点集 内的所有点都联通的情况时最小生成树的总权值和总个数，最后在进行一个背包即可。

具体来说，设 表示加了 条边时，所有联通子图 的最小生成树的总权值总和，这里的 的点集为 ，边集 中的任意一条边 满足 。

考虑转移的时候发现需要记录所有子图 的数量，记为 .

当当前加入的边为 ，边权为 时，转移为：

• 所有集合 有 .
• 对于集合 满足 ，令加上转移：

最后要计算答案，也就是对所有联通子图做一个 0/1 背包，那么枚举每个联通子图，暴力转移即可，设一共有 条边，记 ，设对于点集 ，满足题目条件的总最小生成森林权值和为 ，图的个数为 ，枚举每个联通子图，设为 ，再枚举 ， 为点的全集，有转移：

这样就做完了，答案是 ，时间复杂度 ，常数较大，需要卡一下。另外不要在输入的时候对 取模，会影响边的排序。

struct node {
	int u, v, w;
	node() {}
	node(int _u, int _v, int _w) : u(_u), v(_v), w(_w) {}
};
bool operator < (node A, node B) {
	return A.w < B.w;
}
inline int lowbit(int x) { return x & (-x); }
int n, m, num[1 << 16], inx[1 << 16]; mint dp[1 << 16], f[1 << 16], g[1 << 16], h[1 << 16], inv;
vector<node> E;
inline void solve() {
	cin >> n;
	rep (i, 0, n) rep (j, 0, n) {
		int w; cin >> w; 
		if (w && i < j) m ++ , E.push_back(node(i, j, w));
	}
	inv = q_pow(mint(2));
	sort(E.begin(), E.end());
	int sub = 0;
	rep (S, 1, 1 << n) num[S] = num[S ^ lowbit(S)] + 1, inx[S] = (num[S] == 1);
	rep (i, 0, n) g[1 << i] = 1;
	forn (i, 1, m) {
		int u = E[i - 1].u, v = E[i - 1].v, w = E[i - 1].w % Mod;
		sub |= 1 << u;
		sub |= 1 << v;
		form (S, (1 << n) - 1, 0) if ((S & sub) == S) {
			if ((S >> u & 1) && (S >> v & 1)) {
				g[S] += g[S], dp[S] += dp[S];
				int B = S & ~(1 << u) & ~(1 << v);
				for (int T_sub = B; ; T_sub = (T_sub - 1) & B) {
					int T = (1 << u) | T_sub;
					if (inx[T] && inx[S ^ T]) {
						dp[S] += dp[T] * g[S ^ T] + dp[S ^ T] * g[T] + mint(w) * g[T] * g[S ^ T];
						g[S] += g[T] * g[S ^ T];
					}
					if (T_sub == 0) break;
				}
			}
			inx[S] = 1;
		}
	}
	h[0] = 1;
	int U = (1 << n) - 1;
	rep (S, 0, 1 << n) {
		int card = U ^ S;
		for (int T = card; T; T = (T - 1) & card) {
			f[S + T] += dp[S] * h[T] + f[T] * g[S],
			h[S + T] += h[T] * g[S];
		}
		f[S] += dp[S] * h[0] + f[0] * g[S],
		h[S] += h[0] * g[S];
	}
	cout << f[(1 << n) - 1].r << '\n';
}