给你一个nn个点mm条边的图和一棵nn个点的树，求给树上的点重新标号，标号不能重复，且标号后树上每条边对应在图中都存在的方案数

n≤17,m≤n∗(n−1)2n\le 17, m\le \frac{n*(n-1)}{2}

Luogu P3349

BZOJ4455

Solution

考虑树形Dp

容易想到设dp[x][i]dp[x][i]表示给树上ii号点标jj号的方案数

但是由于标号不能重复，所以必须要再记一维statestate，表示ii的子树的标号集合为statestate，这样才能转移。但是由于这样做需要枚举子集，复杂度不能接受，因此需要优化

注意到，因为有标号不重复（也就是树和图的点需要一一对应）这个条件的限制，才需要枚举子集

那么可以考虑容斥，把这个限制去掉，也就是说有多个点能标同一个标号，这样就很好dp了

先在最外层2n2^n枚举一个标号集合SS，还是设dp[x][i]dp[x][i]表示给树上xx号点标ii号的方案数，那么每次枚举一个i∈Si\in S，暴力枚举xx的儿子yy，并且暴力找出ii在图中所有相邻的点kk，用dp[y][k]dp[y][k]去更新dp[x][i]dp[x][i]的答案即可

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair<int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }

inline void proc_status()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) <<endl;
}

template <typename T> T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

const int Maxn = 17 + 10, Maxm = Maxn * Maxn * 2, Maxs = (1 << 17) + 100;

int N, M;

struct Graph
{
	int e, Begin[Maxn], To[Maxm], Next[Maxm];
	inline void add_edge (int x, int y) { To[++e] = y; Next[e] = Begin[x]; Begin[x] = e; }
}G1, G2;

int A[Maxn], cnt;
LL Dp[Maxn][Maxn];

inline void dfs (int x, int f)
{
	for (int i = G2.Begin[x]; i; i = G2.Next[i]) if (G2.To[i] != f) dfs(G2.To[i], x);

	for (int i = 1; i <= cnt; ++i)
	{
		Dp[x][A[i]] = 1;
		for (int j = G2.Begin[x]; j; j = G2.Next[j])
		{
/**/		int y = G2.To[j];
			if (y == f) continue ;
			LL sum = 0;
			for (int k = G1.Begin[A[i]]; k; k = G1.Next[k]) sum += Dp[y][G1.To[k]];
			Dp[x][A[i]] *= sum;
			if (!sum) break ;
		}
	}
}

inline void Solve ()
{
	int ALL = (1 << N);
	LL ans = 0;
	for (int state = 0; state < ALL; ++state)
	{
		cnt = 0, memset(Dp, 0, sizeof Dp);
		for (int i = 1; i <= N; ++i) if ((1 << (i - 1)) & state) A[++cnt] = i;
		dfs(1, 0);
		LL sum = 0;
		for (int i = 1; i <= cnt; ++i) sum += Dp[1][A[i]];
		if ((N - cnt) & 1) ans -= sum;
		else ans += sum;
	}
	cout<<ans<<endl;
}

inline void Input ()
{
	N = read<int>(), M = read<int>();
	for (int i = 1; i <= M; ++i) { int x = read<int>(), y = read<int>(); G1.add_edge (x, y), G1.add_edge (y, x); }
	for (int i = 1; i < N; ++i) { int x = read<int>(), y = read<int>(); G2.add_edge (x, y), G2.add_edge (y, x); }
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("A.in", "r", stdin);
	freopen("A.out", "w", stdout);
#endif
	Input();
	Solve();
	return 0;
}

Debug

  • 54L：jj写成ii