[原创]ZOJ 3604 Tunnel Network [Prüfer编码与Cayley公式] 【树】

2017-02-07 18:40:56 Tabris_ 阅读数：297

博客爬取于2020-06-14 22:41:49
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/54914010

题目链接 http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3604

---------------------------------------------------------------------------------------------------.
Tunnel Network

Time Limit: 2 Seconds Memory Limit: 65536 KB

Country Far-Far-Away is a big country with N cities. But it is now under a civil war. The rebel uses the ancient tunnel network which connects all N cities with N-1 inter-city tunnels for transportation. The government army want to destroy these tunnels one by one. After several months fighting, some tunnels have been destoryed. According to the intel, the tunnel network have excatly S connected components now. And what government army further knows is that city 1, 2, … , S belong to each of the S connected components. Since the government have little knowledge about the remaining tunnels, they ask you to calculate the number of possible networks of remaining tunnels.

Input
There are multiple test cases. The first line of input contains an integer T (T ≤ 500) indicating the number of test cases. Then T test cases follow.

Each case contains one line containing two integer N (2 ≤ N ≤ 2000) and S (2 ≤ S ≤ N), as described above.

Output
The number of possible networks now. Since the number might be very large, you should output the answer after modulo 1000000007.

Sample Input
4
3 2
4 2
5 3
100 50

Sample Output
2
8
15
113366355

---------------------------------------------------------------------------------------------------.
题目大意:n个城市（标记1…n）由n-1条通道组成，其中的一些通道已经被破坏了，已知现有s个联通，城市1…s分别属于第1…s个联通，想要知道剩下通道网络可能的数目。

解题思路:
Prüfer编码与Cayley公式 from matrix67
明确了上述公式就简单了.

首先要知道Prufer sequence.这是一个双射，能把一棵节点为n个的标号树树唯一映射成一个n-2的序列，反之一个n-2的序列能唯一映射成一个树。这题求树的形态数目可以转化为求序列的数目。
因为是要得到s棵树，所以可以增加一个节点0，让1…s的父节点都为0。Prufer seq是每次找最小的标号，这里每次找最大的标号，本质一样的。
然后就是构造将s+1…n添加到1…s之后的事情。构造如下的图的树：

但是要如何保证构造出来的序列能映射成根为0，第一层为1…s ，剩下的为 s+1…n 呢？
1、序列最后s-1个数字为0,
2、倒数第s个数字在1…s之间
第一个理由是很容易想的。因为我们构造的Prufer seq每次找最大标号的叶子（度为1）节点，所以在第一层的叶子被消去之前第一层以下的所有节点一定会被消去。而1…s的父节点都是0
第二个的话要一点证明：
假如第一层存在一个最大值x（x>s）,那么第一层一下存在一个y（1<=y<=s）。
因为最后s-1个数字都为0，所以x是在y之后被消去的。
假如y的父节点是x：
因为y比第一层之下所有节点标号都大，所以必定是第一层一下所有节点中最后消去的，所以序列倒数第s个数字为x，大于s
假如y的父节点不是x：
那么第一层一下最后一个消去的节点还是x的子节点（条件1）。所以倒数第s个数字还是x，大于s
结论：若第一层中存在最大数字x大于s，则序列的倒数第s个数字必定为x。
所以第二条也是成立的。
然后构造序列就很简单了最后s-1个数字都为0，倒数第s个为1…s，剩下为1…n。
公式： s*n^(n-s-1)
不过当s=n的时候答案为1要另外处理，因为第一层下面没有东西了。

附本题代码
---------------------------------------------------------------------------------------------------.

LL qmod(LL a,LL b){
    LL res=1ll;
    while(b){
        if(b&1) res=res*a%MOD;
        b>>=1;      a=a*a%MOD;
    }
    return res ;
}

int n,s;
LL solve(){
    if(n==s) return 1ll;
    return 1ll*s*qmod(n,n-s-1)%MOD;
}

int main(){
    int _ = 1,kcase = 0;
    while(~scanf("%d",&_)){
        while(_--){
            scanf("%d%d",&n,&s);
            printf("%lld\n",solve());  //在zoj不知为什么 %I64d 会出现PE的情况
        }
    }
    return 0;
}