gym-102956

[toc]

题目链接](https://codeforces.ml/gym/102956))

G. prufer && 树上组合计数问题

当n为奇数时显然为0.

当n为偶数时,首先将n个点分组成两个两个,有$\frac {n!}{(\frac n 2)!2^{\frac n2}}$种 (先排列起来,然后除去n/2组交换顺序的情况,再除去组内的两种组合情况)

上述分式化简结果为$(n-1)!!$

没有想到怎么样直接地化简得来,只能用数学归纳法证明结论的正确性。

另一方面,由凯莱公式可以知道,n/2个节点的带标号完全图生成树有$(\frac n 2) ^ {\frac n 2 -2}$个

而这n/2个”节点”都是由一对真实的单点组成的,所以n/2树上的任意一条边,都是由2个点对组合构成的,共有4种可能的结果。

那么当n/2个点对已经被指定后,该树可能的形态就有$(\frac n 2) ^ {\frac n 2 -2} * 4^{\frac n 2 -1}$种

所以综上考虑,总的方案数就是$(n-1)!! (\frac n 2) ^ {\frac n 2 -2} 4^{\frac n 2 -1}$

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
const int maxn = 5e6 + 10;
int n;
int par[maxn], prufer[maxn], du[maxn];

void encode(){
int ptr = -1;
for(int i = 1; i <= n; i++) if(ptr == -1 && du[i] == 1) ptr = i;

int leaf = ptr;
for(int i = 0; i < n - 2; i++){
int next = prufer[i] = par[leaf];
if(--du[next] == 1 && next < ptr) leaf = next;
else{
ptr++;
while(du[ptr] != 1) ptr++;
leaf = ptr;
}
}
}

void rebuild(){
int ptr = 0;
while(du[ptr] != 1) ptr++;

int leaf = ptr;
for(int i = 0; i < n - 2; i++){
int next = par[leaf] = prufer[i];
if(--du[next] == 1 && next < ptr) leaf = next;
else{
ptr++;
while(du[ptr] != 1) ptr++;
leaf = ptr;
}
}
par[leaf] = n;
}

void hsh(int a[maxn], int n){
ll ans = 0;
for(int i = 0; i < n; i++) ans ^= (i + 1) * 1ll * a[i];
printf("%lld\n", ans);
}

int main(){
// Fastin;

int op;
scanf("%d %d", &n, &op);
if(op == 1){
for(int i = 1; i <= n - 1; i++){
scanf("%d", par + i);
du[par[i]]++; du[i]++;
}
encode();
hsh(prufer, n - 2);
}
else{
for(int i = 1; i <= n; i++) du[i] = 1;
for(int i = 0; i < n - 2; i++){
scanf("%d", prufer + i);
du[prufer[i]]++;
}
rebuild();
hsh(par + 1, n - 1);
}
return 0;
}