[题目链接]( 2020-2021 Winter Petrozavodsk Camp, Belarusian SU Contest (XXI Open Cup, Grand Prix of Belarus))
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}$
cpp
1const int maxn = 5e6 + 10;
2int n;
3int par[maxn], prufer[maxn], du[maxn];
4
5void encode(){
6 int ptr = -1;
7 for(int i = 1; i <= n; i++) if(ptr == -1 && du[i] == 1) ptr = i;
8
9 int leaf = ptr;
10 for(int i = 0; i < n - 2; i++){
11 int next = prufer[i] = par[leaf];
12 if(--du[next] == 1 && next < ptr) leaf = next;
13 else{
14 ptr++;
15 while(du[ptr] != 1) ptr++;
16 leaf = ptr;
17 }
18 }
19}
20
21void rebuild(){
22 int ptr = 0;
23 while(du[ptr] != 1) ptr++;
24
25 int leaf = ptr;
26 for(int i = 0; i < n - 2; i++){
27 int next = par[leaf] = prufer[i];
28 if(--du[next] == 1 && next < ptr) leaf = next;
29 else{
30 ptr++;
31 while(du[ptr] != 1) ptr++;
32 leaf = ptr;
33 }
34 }
35 par[leaf] = n;
36}
37
38void hsh(int a[maxn], int n){
39 ll ans = 0;
40 for(int i = 0; i < n; i++) ans ^= (i + 1) * 1ll * a[i];
41 printf("%lld\n", ans);
42}
43
44int main(){
45// Fastin;
46
47 int op;
48 scanf("%d %d", &n, &op);
49 if(op == 1){
50 for(int i = 1; i <= n - 1; i++){
51 scanf("%d", par + i);
52 du[par[i]]++; du[i]++;
53 }
54 encode();
55 hsh(prufer, n - 2);
56 }
57 else{
58 for(int i = 1; i <= n; i++) du[i] = 1;
59 for(int i = 0; i < n - 2; i++){
60 scanf("%d", prufer + i);
61 du[prufer[i]]++;
62 }
63 rebuild();
64 hsh(par + 1, n - 1);
65 }
66 return 0;
67}