2018 Wannafly summer camp Day3-- Travel (思维 组合数取模)

题目链接：https://www.nowcoder.com/acm/contest/203/H

题目大意：

       魔方国有n座城市，编号为。城市之间通过n-1条无向道路连接，形成一个树形结构。澜澜打算在魔方国进行m次旅游，每次游览至少一座城市。为了方便，每次旅游游览的城市必须是连通的。此外，澜澜希望游览所有城市恰好一次。
       澜澜想知道有多少种旅游方案满足条件，两个方案不同当且仅当存在某一次旅游游览了不同的城市。澜澜不会数数，所以只好让你来帮他数方案。

题解：

      第一次见到披着树形结构的外衣却与树完全不相干的题。

      首先给了n个点，n-1条边，那么肯定是一棵树。进行m次旅行，每个点都要经过且只能经过一次，那就是用m条边将n个点分为m段，这里就是隔板法的思想，划分数就是(将n个点划分为m段，就是在n-1个空中插入m-1个板)。

----------------------------------------------------------------------------

      在网上也看了一些题解，都是一个版本的，感觉并没有说的很清楚。我认为本题应该是划分点而不是划分边，即划分n个点而不是n-1条边，因为并不一定所有点都在一条边上。

      比如这个图，将6个点的树划分为3段，那么左边那一段是不可能通过一次旅行来走完的。所以划分边不行，需要划分点。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#define mod 1000000007
using namespace std;
typedef long long ll;
#define maxn 1000010
int t, n, m, ta, tb;
ll c[maxn];
long long pow_mod(long long a,long long n,long long m)//a^n mod m
{long long res=1;while(n>0){if(n&1==1)res=res*a%m;a=a*a%m;n>>=1;}return res;
}
//记得在最后输出结果的时候再模m一次void init()//先打出阶乘，节省时间
{c[1] = 1;for (int i = 2; i <= maxn; i++)c[i] = c[i - 1] * i%mod;
}
ll C(ll n, ll m)
{return c[n] * pow_mod(c[m] * c[n - m] % mod, mod - 2, mod) % mod;
}
int main()
{init();int T,x,y;cin>>T;while(T--){cin>>n>>m;for(int i = 0; i < n - 1; i++)cin>>x>>y;if(m == 1){puts("1");continue;}ll ans = C(n, m);ans = (ans*c[m]) % mod;cout << ans << endl;}return 0;
}