ZJOI2016 小星星

Vexoben

Feb 20, 2019

It takes 4 minutes to read this article.

题目链接:uoj185

(刷新以获取数学公式)

题意

给定一张 $n$ 个点的图和 $n$ 个点的树,问两张图的点有多少种对应关系,使树是图的子图.

题解

显然可以想一个 $n^3*3^n$ 的DP: $f[i][j][k]$ 表示 $i$ 这颗子树, $i$ 点对应图上点 $j$ ,子树中的点对应图上点集 $k$ 的方案数,然而能拿的分好像和暴力差不多.不过听说转移FMT优化一下可以做到 $n^3*2^n$ ,然而被卡常也不是很能过.

标算是一个 $n^3*2^n$ 的容斥.如果我们不要求树和图上的点一一对应,而是多个树上的点可以对应同一个图上的点,只要对应后的点之间有边即可,DP的复杂度可以降低为 $O(n^3)$

枚举映射到的点集,那么答案就是 $ans(bitcnt[S] = n) - ans(bitcnt[S] = n-1) + ...$

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 17;

int n, m, E, lim;
int a[N][N], bitcnt[1 << N];
int fir[N], nex[N << 1], arr[N << 1];
LL f[N][N];

inline void Add_Edge(int x, int y) {
	nex[++E] = fir[x];
	fir[x] = E; arr[E] = y;
}

void dfs(int x, int fa) {
	for (int i = 0; i < n; ++i) {
		if (lim >> i & 1) f[x][i] = 1;
	}
	for (int i = fir[x]; i; i = nex[i]) {
		if (arr[i] == fa) continue;
		dfs(arr[i], x);
		for (int j = 0; j < n; ++j) {
			if (~lim >> j & 1) continue;
			LL tmp = 0;
			for (int k = 0; k < n; ++k) {
				if (a[j][k] && (lim >> k & 1)) {
					tmp += f[arr[i]][k];
				}
			}
			f[x][j] *= tmp;
		}
	}
}

LL calc() {
	LL ans = 0;
	memset(f, 0, sizeof f);
	dfs(0, -1);
	for (int i = 0; i < n; ++i) {
		if (lim >> i & 1) {
			ans += f[0][i];
		}
	}
	return ans;
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; ++i) {
		int x, y;
		scanf("%d%d", &x, &y);
		--x; --y;
		a[x][y] = a[y][x] = 1;
	}
	for (int i = 1; i < n; ++i) {
		int x, y;
		scanf("%d%d", &x, &y);
		--x; --y;
		Add_Edge(x, y);
		Add_Edge(y, x);
	}
	for (int i = 0; i < (1 << n); ++i) {
		bitcnt[i] = (bitcnt[i >> 1]) + (i & 1);
	}
	LL ans = 0;
	for (lim = 0; lim < (1 << n); ++lim) {
		LL tmp = calc();
		ans += (bitcnt[lim] & 1) ? tmp : -tmp;
	}
	printf("%lld\n", abs(ans));
	return 0;
}