BZOJ 1005: [HNOI2008]明明的烦恼

Description

自从明明学了树的结构,就对奇怪的树产生了兴趣……给出标号为1到N的点,以及某些点最终的度数,允许在

任意两点间连线,可产生多少棵度数满足要求的树?

Input

第一行为N(0 < N < = 1000),

接下来N行,第i+1行给出第i个节点的度数Di,如果对度数不要求,则输入-1

Output

一个整数,表示不同的满足要求的树的个数,无解输出0

Sample Input

-1

Sample Output

HINT

两棵树分别为1-2-3;1-3-2

Source

Solution

这里要用到prufer序列的相关知识。

prufer序列知识：

将树转化成Prufer数列的方法

一种生成Prufer序列的方法是迭代删点，直到原图仅剩两个点。对于一棵顶点已经经过编号的树T，顶点的编号为{1,2,…,n}，在第i步时，移去所有叶子节点（度为1的顶点）中标号最小的顶点和相连的边，并把与它相邻的点的编号加入Prufer序列中，重复以上步骤直到原图仅剩2个顶点。

将Prufer数列转化成树的方法

设{a1,a2,..an-2}为一棵有n个节点的树的Prufer序列，另建一个集合G含有元素{1..n}，找出集合中最小的未在Prufer序列中出现过的数，将该点与Prufer序列中首项连一条边，并将该点和Prufer序列首项删除，重复操作n-2次，将集合中剩余的两个点之间连边即可。

先甩出一个结论：prufer序列中每个点出现次数+1等于这个点的度数。

证明从prufer序列的构造上来考虑，一个节点的每一个孩子都会visit一下这个点他到父亲的那条边不会被考虑最后剩下的两点看作互为父亲。

于是不难发现一个无根树对应一个prufer序列一个prufer序列对应一个无根树

现在就是用这些点的度数构造prufer。

一共是n-2个位置可以写数我们记\( sum = \sum_i d_i-1 \) 答案就是\( \frac {(n-2)!*m^{n-2-sum}}{(n-2-sum)!\prod_i (d_i-1)!} \)

用分解质因子来做乘除法最后高精求答案。

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
#include <cstdio>
#include <algorithm>
using namespace std;
const int c = 168;
int p[c] = {
	2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
	43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,
	101, 103, 107, 109, 113, 127, 131, 137, 139, 149,
	151, 157, 163, 167, 173, 179, 181, 191, 193, 197,
	199, 211, 223, 227, 229, 233, 239, 241, 251, 257,
	263, 269, 271, 277, 281, 283, 293, 307, 311, 313,
	317, 331, 337, 347, 349, 353, 359, 367, 373, 379,
	383, 389, 397, 401, 409, 419, 421, 431, 433, 439,
	443, 449, 457, 461, 463, 467, 479, 487, 491, 499,
	503, 509, 521, 523, 541, 547, 557, 563, 569, 571,
	577, 587, 593, 599, 601, 607, 613, 617, 619, 631,
	641, 643, 647, 653, 659, 661, 673, 677, 683, 691,
	701, 709, 719, 727, 733, 739, 743, 751, 757, 761,
	769, 773, 787, 797, 809, 811, 821, 823, 827, 829,
	839, 853, 857, 859, 863, 877, 881, 883, 887, 907,
	911, 919, 929, 937, 941, 947, 953, 967, 971, 977,
	983, 991, 997};
int n, cnt[c], A[100000], tot, d[1005];
int calc(int x, int y) {
	int ret = 0;
	while (x >= y) {
		ret += x / y;
		x /= y;
	}
	return ret;
}
void deco(int x, int d) {
	for (int i = 0; i < c && p[i] <= x; ++i)
		cnt[i] += d * calc(x, p[i]);
}
void mul(int val) {
	for (int i = 1; i <= tot; ++i) A[i] *= val;
	for (int i = 1; i <= tot; ++i) {
		A[i+1] += A[i] / 10;
		A[i] %= 10;
	}
	if (A[tot+1] > 0) ++tot;
	while (A[tot] > 9) {
		A[tot+1] = A[tot] / 10;
		A[tot++] %= 10;
	}
}
int calc2(int &x, int p) {
	int ret = 0;
	while (x % p == 0) {
		x /= p;
		++ret;
	}
	return ret;
}
int main() {
	scanf("%d", &n);
	int m = 0, sum = 0;
	for (int i = 0; i < n; ++i) {
		scanf("%d", d + i);
		if (d[i] == 0) { putchar('0'); return 0; }
		if (d[i] == -1) ++m;
		else { --d[i]; sum += d[i]; }
	}
	if (sum > n - 2) { putchar('0'); return 0; }
	for (int i = 0; i < c; ++i) if (m % p[i] == 0) cnt[i] += (n - 2 - sum) * calc2(m, p[i]);
	deco(n - 2, 1);
	deco(n - 2 - sum, -1);
	A[1] = tot = 1;
	for (int i = 0; i < n; ++i) if (d[i] > 0) deco(d[i], -1);
	for (int i = 0; i < c; ++i) {
		if (cnt[i] < 0) { putchar('0'); return 0; }
		for (int j = 0; j < cnt[i]; ++j)
			mul(p[i]);
	}
	for (int i = tot; i >= 1; --i) printf("%d", A[i]);
}

树转prufer序列代码：

 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
#include <queue>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 100005;
bool vis[maxn], deled[maxn << 1];
int cnte, h[maxn], digree[maxn], n, x, y, now;
priority_queue<int, vector<int>, greater<int> > Q;
struct edge_t { int to, succ, prev; } edge[maxn << 1];
void ins(int x, int y) {
	edge[++cnte].to = y;
	edge[cnte].prev = h[x];
	edge[h[x]].succ = cnte;
	h[x] = cnte;
	++digree[y];
}
void del(int eid) {
	--digree[edge[eid].to]; deled[eid] = true;
	if (!vis[edge[eid].to] && digree[edge[eid].to] == 1) Q.push(edge[eid].to);
	if (edge[eid].prev) edge[edge[eid].prev].succ = edge[eid].succ;
	if (edge[eid].succ) edge[edge[eid].succ].prev = edge[eid].prev;
}
int main() {
	scanf("%d", &n); cnte = 1;
	for (int i = 1; i < n; ++i) {
		scanf("%d %d", &x, &y);
		ins(x, y); ins(y, x);
	}
	for (int i = 1; i <= n; ++i) if (digree[i] == 1) Q.push(i);
	for (int i = 2; i < n; ++i) {
		now = Q.top(); Q.pop(); vis[now] = true;
		while (deled[h[now]]) h[now] = edge[h[now]].prev;
		printf("%d ", edge[h[now]].to);
		del(h[now]); del(h[now]^1);
	}
}