!!!! 摘自

題目鏈接 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條通道組成，其中的一些通道已經(jīng)被破壞了，已知現(xiàn)有s個聯(lián)通，城市1…s分別屬于第1…s個聯(lián)通，想要知道剩下通道網(wǎng)絡(luò)可能的數(shù)目。

解題思路: Prüfer編碼與Cayley公式 from matrix67 明確了上述公式就簡單了.

首先要知道Prufer sequence.這是一個雙射，能把一棵節(jié)點為n個的標號樹樹唯一映射成一個n-2的序列，反之一個n-2的序列能唯一映射成一個樹。這題求樹的形態(tài)數(shù)目可以轉(zhuǎn)化為求序列的數(shù)目。 因為是要得到s棵樹，所以可以增加一個節(jié)點0，讓1…s的父節(jié)點都為0。Prufer seq是每次找最小的標號，這里每次找最大的標號，本質(zhì)一樣的。 然后就是構(gòu)造將s+1…n添加到1…s之后的事情。構(gòu)造如下的圖的樹： 但是要如何保證構(gòu)造出來的序列能映射成根為0，第一層為1…s ， 剩下的為 s+1…n 呢？ 1、序列最后s-1個數(shù)字為0, 2、倒數(shù)第s個數(shù)字在1…s之間 第一個理由是很容易想的。因為我們構(gòu)造的Prufer seq每次找最大標號的葉子（度為1）節(jié)點，所以在第一層的葉子被消去之前第一層以下的所有節(jié)點一定會被消去。而1…s的父節(jié)點都是0 第二個的話要一點證明： 假如第一層存在一個最大值x（x>s）,那么第一層一下存在一個y（1<=y<=s）。 因為最后s-1個數(shù)字都為0，所以x是在y之后被消去的。 假如y的父節(jié)點是x： 因為y比第一層之下所有節(jié)點標號都大，所以必定是第一層一下所有節(jié)點中最后消去的，所以序列倒數(shù)第s個數(shù)字為x，大于s 假如y的父節(jié)點不是x： 那么第一層一下最后一個消去的節(jié)點還是x的子節(jié)點（條件1）。所以倒數(shù)第s個數(shù)字還是x，大于s 結(jié)論： 若第一層中存在最大數(shù)字x大于s，則序列的倒數(shù)第s個數(shù)字必定為x。 所以第二條也是成立的。 然后構(gòu)造序列就很簡單了最后s-1個數(shù)字都為0，倒數(shù)第s個為1…s，剩下為1…n。 公式 ： s*n^(n-s-1) 不過當(dāng)s=n的時候答案為1要另外處理，因為第一層下面沒有東西了。

附本題代碼 —————————————————————————————————.