题解
设 (f(S,u,x)) 表示树上点 (u) 映射到图上点 (x) ,且图上 (S) 中的点都被 (u) 的子树映射,且 (S) 中的点在图中连通时的方案树。
枚举 (u) 的儿子 (v) , (v) 映射到 (y) 满足 ((x,y) in E) ,显然有一个类似树形背包的式子 (f(S,u,x) gets sumlimits_{x
otin T,yin T} f(S - T,u,x) imes f(T,v,y)) 。
则 (ans = sumlimits_{x=1}^{n} f(V,1,x)) 。
然而这样做是 (O(3^nn^3)) 的,显然会T。
#include <cstdio>
#define MAX_N (17 + 5)
#define MAX_S ((1 << 17) + 5)
int n, m;
int lim;
int h1[MAX_N], h2[MAX_N], tot;
struct Edge {
int to, next;
} e[MAX_N * MAX_N];
long long f[MAX_S][MAX_N][MAX_N];
void Add_Edge(int u, int v, int *h) {
e[++tot].to = v;
e[tot].next = h[u];
h[u] = tot;
}
void DFS(int u, int fa) {
for (int i = h2[u], v; i; i = e[i].next) {
v = e[i].to;
if (v == fa) continue;
DFS(v, u);
for (int S = lim; S; --S) {
for (int T = S - 1 & S; T; T = T - 1 & S) {
for (int x = 1; x <= n; ++x) {
if (!(1 << x - 1 & (S ^ T))) continue;
for (int j = h1[x], y; j; j = e[j].next) {
y = e[j].to;
if (!(1 << y - 1 & T)) continue;
f[S][u][x] += f[S ^ T][u][x] * f[T][v][y];
}
}
}
}
}
}
int main() {
scanf("%d%d", &n, &m);
lim = (1 << n) - 1;
int u, v;
for (int i = 1; i <= m; ++i) {
scanf("%d%d", &u, &v);
Add_Edge(u, v, h1);
Add_Edge(v, u, h1);
}
for (int i = 1; i < n; ++i) {
scanf("%d%d", &u, &v);
Add_Edge(u, v, h2);
Add_Edge(v, u, h2);
}
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
f[1 << j - 1][i][j] = 1;
DFS(1, 0);
long long ans = 0;
for (int i = 1; i <= n; ++i)
ans += f[lim][1][i];
printf("%lld", ans);
return 0;
}
考虑最浪费时间的就是 (O(3^n)) 的枚举子集。
考虑去掉 (S) 这一维后求 (f(u,x)) 为什么不对?
其实是这里算的方案中 (exists u
ot = v,u o x,v o x) ,而题目中要求树与图上的点一一对应,不能重复,所以这样做是错的。
那么考虑容斥,实际上我们可以设 (g(S,u,x)) 为 (u o x) 且映射到的点属于 (S) 的情况下的方案数,也就是说 (S) 中的点不一定与 (u) 的子树上的点一一对应,而且 (u) 子树上的点不一定都有映射。
显然 (g(S,u,x) = prodlimits_{vinmathrm{son}(u)} left( sumlimits_{(x,y) in E} g(S,v,y)
ight)) 。
对于每一个 (S) ,都可以以 (O(n^3)) 的时间复杂度求出所有 (g(S,u,x)) 。
我们知道子集反演 (g(S) = sumlimits_{T subseteq S} f(T) Leftrightarrow f(S) = sumlimits_{T subseteq S} (-1)^{|S| - |T|} g(T)) (其实就是容斥)。
则 (f(S,u,x) = sumlimits_{T subseteq S} (-1)^{|S| - |T|} g(T,u,x)) 。
故 (ans = sumlimits_{x=1}^{n} f(V,1,x) = sumlimits_{S subseteq V}sumlimits_{x=1}^{n} (-1)^{n - |S|} g(S,1,x)) 。
于是先 (O(2^n)) 枚举 (S) 然后再dp,总复杂度就是 (O(2^nn^3)) ,吸口氧就过了。
#include <cstdio>
#include <cstring>
#define MAX_N (17 + 5)
int n, m;
int lim;
int h1[MAX_N], h2[MAX_N], tot;
struct Edge {
int to, next;
} e[MAX_N * MAX_N];
int q[MAX_N], len;
long long f[MAX_N][MAX_N];
void Add_Edge(int u, int v, int *h) {
e[++tot].to = v;
e[tot].next = h[u];
h[u] = tot;
}
void DFS(int u, int fa, int S) {
long long sum;
for (int i = h2[u], v; i; i = e[i].next) {
v = e[i].to;
if (v == fa) continue;
DFS(v, u, S);
for (int x = 1; x <= n; ++x) {
if (!(1 << x - 1 & S)) continue;
sum = 0;
for (int j = h1[x], y; j; j = e[j].next) {
y = e[j].to;
if (!(1 << y - 1 & S)) continue;
sum += f[v][y];
}
f[u][x] *= sum;
}
}
}
int main() {
scanf("%d%d", &n, &m);
lim = (1 << n) - 1;
int u, v;
for (int i = 1; i <= m; ++i) {
scanf("%d%d", &u, &v);
Add_Edge(u, v, h1);
Add_Edge(v, u, h1);
}
for (int i = 1; i < n; ++i) {
scanf("%d%d", &u, &v);
Add_Edge(u, v, h2);
Add_Edge(v, u, h2);
}
long long ans = 0;
for (int S = 1; S <= lim; ++S) {
memset(f, 0, sizeof f);
len = 0;
for (int i = 1; i <= n; ++i)
if (1 << i - 1 & S) q[++len] = i;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= len; ++j)
f[i][q[j]] = 1;
DFS(1, 0, S);
if (n - len & 1)
for (int i = 1; i <= len; ++i)
ans -= f[1][q[i]];
else
for (int i = 1; i <= len; ++i)
ans += f[1][q[i]];
}
printf("%lld", ans);
return 0;
}