BZOJ 1005: [HNOI2008]明明的烦恼

Description

自从明明学了树的结构,就对奇怪的树产生了兴趣……给出标号为1到N的点,以及某些点最终的度数,允许在
任意两点间连线,可产生多少棵度数满足要求的树?

Input

第一行为N(0 < N < = 1000),
接下来N行,第i+1行给出第i个节点的度数Di,如果对度数不要求,则输入-1

Output

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

Sample Input

3
1
-1
-1

Sample Output

2

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

#include <cstdio>
#include <algorithm>
using namespace std;
const int c = 168;
int p = {
	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, 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序列代码:

#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);
	}
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据