!!!! 摘自

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

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

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

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