题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5378
题意：给你一棵n个结点的有根树。因为是有根树，那么每个结点可以指定以它为根的子树（后面讨论的子树都是这个）。现在我们把标号从1到n的n个minister派驻到这些结点上面（每个结点派驻一人），并规定任一子树中编号最大的minister 为该子树的领导，问你存在多少个不同的领导
解：
引用官方题解：
可以用求概率的思想来解决这个问题。令以i号节点为根的子树为第i棵子树，设这颗子树恰好有sz[i]个点。那么第i个点是第i棵子树最大值的概率为1/sz[i]，不是最大值的概率为(sz[i]-1)/sz[i]。现在可以求解恰好有k个最大值的概率。 令dp[i][j]表示考虑编号从1到i的点，其中恰好有j个点是其子树最大值的概率。 很容易得到如下转移方程：dp[i][j]=dp[i-1][j]*(sz[i]-1)/sz[i]+dp[i-1][j-1]/sz[i]。这样dp[n][k]就是所有点中恰好有k个最大值的概率。 题目要求的是方案数，用总数n！乘上概率就是答案。计算的时候用逆元代替上面的分数即可
/*
* Problem: hdu5378 Leader in Tree Land
* Author: SHJWUDP
* Created Time: 2015/8/12 星期三 20:17:31
* File Name: 1006.cpp
* State: Accepted
* Memo: 概率dp，乘法逆元
*/
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm> using namespace std; const int MOD=1e9+; struct Edge {
int u, v;
}; int n, k;
vector<Edge> edges;
vector<vector<int> > G;
vector<int> siz, inv; ///siz[i]*inv[i]=1(mod 1e9+7)
void init() {
edges.clear();
G.assign(n+, vector<int>());
siz.resize(n+);
inv.resize(n+);
}
void addEdge(int u, int v) {
edges.push_back((Edge){u, v});
G[u].push_back(edges.size()-);
}
int pow_mod(long long x, int n, int mod) {
long long res=;
while(n) {
if(n & ) res=res*x%mod;
x=x*x%mod;
n>>=;
}
return res;
}
void dfs(int u, int fa) {
siz[u]=;
for(int i : G[u]) {
Edge & e=edges[i];
if(e.v==fa) continue;
dfs(e.v, u);
siz[u]+=siz[e.v];
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in", "r", stdin);
//freopen("out", "w", stdout);
#endif
int T, now=;
scanf("%d", &T);
while(T--) {
scanf("%d%d", &n, &k);
init();
for(int i=; i<n-; i++) {
int a, b;
scanf("%d%d", &a, &b);
addEdge(a, b);
addEdge(b, a);
}
dfs(, -);
for(int i=; i<=n; i++) inv[i]=pow_mod(siz[i], MOD-, MOD); //求siz[i]的乘法逆元
vector<vector<long long> > f(n+, vector<long long>(n+, ));
f[][]=;
for(int i=; i<=n; i++) {
for(int j=; j<=k; j++) {
f[i][j]+=f[i-][j]*(siz[i]-)%MOD*inv[i]%MOD;
if(j>)f[i][j]+=f[i-][j-]*inv[i]%MOD;
f[i][j]%=MOD;
}
}
long long ans=f[n][k];
for(int i=; i<=n; i++) {
ans=(ans*i)%MOD;
}
printf("Case #%d: ", ++now);
printf("%I64d\n", ans);
}
return ;
}