P3349 [ZJOI2016]小星星

给定一个图，和一棵树，点数一样，求把树映射到图上的方案。

可以想到用(f[i][j][k])表示树上i映射到图上j，子树集合为k的状压
要枚举子集，自己和每个儿子，还要遍历一次树
所以时间复杂度是(O(n^3 imes 3^n))
正解状压还没搞出来。咕咕

const int N = 19;
int n, m;
namespace brute {
	std::bitset<N> b[N], c[N];
	int a[N];
	std::map<std::pair<int, int>, int> mp;
	int main() {
		read(n);
		read(m);
		int x, y,ans(0);
		rep(i, 1, m) {
			read(x);
			read(y);
			b[x][y] = b[y][x] = 1;
		}
		rep(i, 2, n) {
			read(x);
			read(y);
			mp[ {x, y}] = mp[ {y, x}] = 1;
		}

		rep(i, 1, n) {
			a[i] = i;
		}
		do {
			bool flag(1);
			for(auto j : mp) {
				auto t = j.first.second;
				auto tt = j.first.first;
				t = a[t];
				tt = a[tt];
				flag &= b[t][tt];
				if(!flag) break;
			}
			ans += flag;
		} while(std::next_permutation(a + 1, a + n + 1));
		out(ans, '
');
		return 0;
	}
}
namespace solve1 {

	int mx;
	struct graph {
		int head[N], tot, next[N * N << 1], ver[N * N << 1];
		inline void add(int a, int b) {
			ver[++tot] = b;
			next[tot] = head[a];
			head[a] = tot;
		}
	} G, C;
	int f[N][N][1 << 19];
	std::vector<int> sta[N];
	int siz[N];
	inline void dfs(int x, int fa) {
		siz[x] = 1;
		rep(i, 1, n) {
			f[x][i][1 << (i - 1)] = 1;//初始化
		}

		repc(x) {
			int y(C.ver[j]);
			if(y == fa) continue;
			dfs(y, x);
 
			rep(id, 1, n) {//枚举x映射的点id
				for(auto S : sta[siz[x]]) {
					if( !((S >> (id - 1)) & 1))  continue;//所选的集合必须要有id
					repg(id) {
						int yy = G.ver[i];
						if((S >> (yy - 1)) & 1) continue;//俩集合必须不交

						for(auto K : sta[siz[y]]) {
							if(S & K || !((K >> (yy - 1) ) ) ) continue;
							f[x][id][S | K] += f[x][id][S] * f[y][yy][K];//合成
						}
					}
				}
			}
			siz[x] += siz[y];
		}
	}


	int main() {
		read(n);
		read(m);

		mx = (1 << n) - 1;

		int x, y;
		rep(i, 1, m) {
			read(x);
			read(y);
			G.add(x, y);
			G.add(y, x);
		}

		rep(i, 2, n) {
			read(x);
			read(y);
			C.add(x, y);
			C.add(y, x);
		}

		rep(i, 0, mx) {
			int x = __builtin_popcount(i);
			sta[x].push_back(i);
		}

		dfs(1, 0);
		__int128 ans(0);
		rep(i, 1, n) {
			ans += f[1][i][mx];
		}
		out(ans, '
');
		return 0;
	}
}