题解 P4981 【父子】

· · 题解

楼下的巨佬都没有详细讲证明啊，在此我简单说一下详细证明

【思路】

这道题经过建模易得出，我们要求的就是有n个节点的有根树可能的形态数。

最后得出一个公式（有证明）

ans = n^{n - 1}

代码就出来了，不过重要的是证明部分

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define MOD 1000000009
LL ksm(LL n, LL m)
{//快速幂
    LL ret = 1;
    while(m) 
    {
        if(m & 1) ret = (ret * n) % MOD;
        n = (n * n) % MOD;
        m >>= 1;
    }
    return ret;
}
int main()
{
    int k;
    scanf("%d", &k);
    while(k --) 
    {
        LL n;
        scanf("%lld", &n);
        printf("%lld\n", ksm(n, n-1));
    }
}

【证明】（重点）

p.s 学习自https://www.cnblogs.com/dirge/p/5503289.html

首先引入prufer编码（这个单词的正确写法不是这样，但是很难打出来，以下以此代称）

一棵无根树的prufer编码的值运算如下：

首先定义无根树中度数为1的节点是叶子节点。
找到编号最小的叶子并删除，序列中添加与之相连的节点编号，重复执行直到只剩下2个节点。

（转载自https://www.cnblogs.com/dirge/p/5503289.html）

举个例子，对于下图的树

它的prufer编码就是4, 3, 3

显然，一棵有n个结点的无根树，它的prufer编码是唯一的，且有n-2个可能相同的元素。

那么如何由一个prufer编码转化为二叉树？

那个博客上的巨佬是这么说的：

设点集V={1,2,3,...,n}，每次取出prufer序列中最前面的元素u，在V中找到编号最小的没有在prufer序列中出现的元素v，给u，v连边然后分别删除，最后在V中剩下两个节点，给它们连边。最终得到的就是无根树。

很显然，每一个prufer序列与一棵无根树一一对应。

因此，对于一棵已知有n个结点的无根树，一定有一个n-2长度的序列，那么，我们枚举所有长度为n-2的序列，发现其与所有可能形态的无根树一一对应。而这种序列，根据乘法原理，有

n ^{n - 2}

个可能的序列。

因此，对于一个已知的n，有n^{n-2}种不同的无根树。

而由于无根树没有根，而题目要求的是有根树，因此，对于一棵n个结点的无根树，我们有n种选根的可能。

因此，对于一个已知的n，有n^{n-2} * n即n ^ {n-1}种不同的有根树。

证毕。